# Find two equal subsequences of maximum length with at least one different index

Given a string **str**, the task is to find the maximum length **K** such that there exist two sub-sequences **A** and **B** each of length **K** such that **A = B** and number of common indices between **A** and **B** is at most **K – 1**.**Examples:**

Input:str = “geeksforgeeks”Output:12

The two subsequences are

str[0…1] + str[3…12] = “geksforgeeks”

and str[0] + str[2…12] = “geksforgeeks”.Input:str = “abcddefg”Output:7

**Approach:** Find any pair of the same letter with a minimum number of letters between them let say this minimum number be **X**, now the answer of the problem is **len(str) – (X + 1)**. One is added in **X** to not take count of one letter from the pair.

Below is the implementation of the above approach:

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `const` `int` `MAX = 26;` `// Function to return the required` `// length of the subsequences` `int` `maxLength(string str, ` `int` `len)` `{` ` ` `// To store the result` ` ` `int` `res = 0;` ` ` `// To store the last visited` ` ` `// position of lowercase letters` ` ` `int` `lastPos[MAX];` ` ` `// Initialisation of frequency array to -1 to` ` ` `// indicate no character has previously occured` ` ` `for` `(` `int` `i = 0; i < MAX; i++) {` ` ` `lastPos[i] = -1;` ` ` `}` ` ` `// For every character of the string` ` ` `for` `(` `int` `i = 0; i < len; i++) {` ` ` `// Get the index of the current character` ` ` `int` `C = str[i] - ` `'a'` `;` ` ` `// If the current character has` ` ` `// appeared before in the string` ` ` `if` `(lastPos[C] != -1) {` ` ` `// Update the result` ` ` `res = max(len - (i - lastPos[C] - 1) - 1, res);` ` ` `}` ` ` `// Update the last position` ` ` `// of the current character` ` ` `lastPos[C] = i;` ` ` `}` ` ` `return` `res;` `}` `// Driver code` `int` `main()` `{` ` ` `string str = ` `"geeksforgeeks"` `;` ` ` `int` `len = str.length();` ` ` `cout << maxLength(str, len);` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the approach` `class` `GFG` `{` ` ` `static` `int` `MAX = ` `26` `;` `// Function to return the required` `// length of the subsequences` `static` `int` `maxLength(String str, ` `int` `len)` `{` ` ` `// To store the result` ` ` `int` `res = ` `0` `;` ` ` `// To store the last visited` ` ` `// position of lowercase letters` ` ` `int` `lastPos[] = ` `new` `int` `[MAX];` ` ` `// Initialisation of frequency array to -1 to` ` ` `// indicate no character has previously occured` ` ` `for` `(` `int` `i = ` `0` `; i < MAX; i++)` ` ` `{` ` ` `lastPos[i] = -` `1` `;` ` ` `}` ` ` `// For every character of the String` ` ` `for` `(` `int` `i = ` `0` `; i < len; i++)` ` ` `{` ` ` `// Get the index of the current character` ` ` `int` `C = str.charAt(i) - ` `'a'` `;` ` ` `// If the current character has` ` ` `// appeared before in the String` ` ` `if` `(lastPos[C] != -` `1` `)` ` ` `{` ` ` `// Update the result` ` ` `res = Math.max(len - (i -` ` ` `lastPos[C] - ` `1` `) - ` `1` `, res);` ` ` `}` ` ` `// Update the last position` ` ` `// of the current character` ` ` `lastPos[C] = i;` ` ` `}` ` ` `return` `res;` `}` `// Driver code` `public` `static` `void` `main(String args[])` `{` ` ` `String str = ` `"geeksforgeeks"` `;` ` ` `int` `len = str.length();` ` ` `System.out.println(maxLength(str, len));` `}` `}` `// This code is contributed by Arnab Kundu` |

## Python3

`# Python implementation of the approach` `MAX` `=` `26` `;` `# Function to return the required` `# length of the subsequences` `def` `maxLength(` `str` `, ` `len` `):` ` ` `# To store the result` ` ` `res ` `=` `0` `;` ` ` `# To store the last visited` ` ` `# position of lowercase letters` ` ` `lastPos ` `=` `[` `0` `] ` `*` `MAX` `;` ` ` `# Initialisation of frequency array to -1 to` ` ` `# indicate no character has previously occured` ` ` `for` `i ` `in` `range` `(` `MAX` `):` ` ` `lastPos[i] ` `=` `-` `1` `;` ` ` ` ` `# For every character of the String` ` ` `for` `i ` `in` `range` `(` `len` `):` ` ` `# Get the index of the current character` ` ` `C ` `=` `ord` `(` `str` `[i]) ` `-` `ord` `(` `'a'` `);` ` ` `# If the current character has` ` ` `# appeared before in the String` ` ` `if` `(lastPos[C] !` `=` `-` `1` `):` ` ` `# Update the result` ` ` `res ` `=` `max` `(` `len` `-` `(i ` `-` `lastPos[C] ` `-` `1` `) ` `-` `1` `, res);` ` ` ` ` `# Update the last position` ` ` `# of the current character` ` ` `lastPos[C] ` `=` `i;` ` ` ` ` `return` `res;` `# Driver code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `str` `=` `"geeksforgeeks"` `;` ` ` `len` `=` `len` `(` `str` `);` ` ` `print` `(maxLength(` `str` `, ` `len` `));` `# This code is contributed by 29AjayKumar` |

## C#

`// C# implementation of the approach` `using` `System;` `class` `GFG` `{` ` ` ` ` `static` `int` `MAX = 26;` ` ` ` ` `// Function to return the required` ` ` `// length of the subsequences` ` ` `static` `int` `maxLength(` `string` `str, ` `int` `len)` ` ` `{` ` ` `// To store the result` ` ` `int` `res = 0;` ` ` ` ` `// To store the last visited` ` ` `// position of lowercase letters` ` ` `int` `[]lastPos = ` `new` `int` `[MAX];` ` ` ` ` `// Initialisation of frequency array to -1 to` ` ` `// indicate no character has previously occured` ` ` `for` `(` `int` `i = 0; i < MAX; i++)` ` ` `{` ` ` `lastPos[i] = -1;` ` ` `}` ` ` ` ` `// For every character of the String` ` ` `for` `(` `int` `i = 0; i < len; i++)` ` ` `{` ` ` ` ` `// Get the index of the current character` ` ` `int` `C = str[i] - ` `'a'` `;` ` ` ` ` `// If the current character has` ` ` `// appeared before in the String` ` ` `if` `(lastPos[C] != -1)` ` ` `{` ` ` ` ` `// Update the result` ` ` `res = Math.Max(len - (i -` ` ` `lastPos[C] - 1) - 1, res);` ` ` `}` ` ` ` ` `// Update the last position` ` ` `// of the current character` ` ` `lastPos[C] = i;` ` ` `}` ` ` `return` `res;` ` ` `}` ` ` ` ` `// Driver code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `string` `str = ` `"geeksforgeeks"` `;` ` ` `int` `len = str.Length;` ` ` ` ` `Console.WriteLine(maxLength(str, len));` ` ` `}` `}` `// This code is contributed by AnkitRai01` |

## Javascript

`<script>` `// Javascript implementation of the approach` `var` `MAX = 26;` `// Function to return the required` `// length of the subsequences` `function` `maxLength(str, len)` `{` ` ` `// To store the result` ` ` `var` `res = 0;` ` ` `// To store the last visited` ` ` `// position of lowercase letters` ` ` `var` `lastPos = Array(MAX);` ` ` `// Initialisation of frequency array to -1 to` ` ` `// indicate no character has previously occured` ` ` `for` `(` `var` `i = 0; i < MAX; i++) {` ` ` `lastPos[i] = -1;` ` ` `}` ` ` `// For every character of the string` ` ` `for` `(` `var` `i = 0; i < len; i++) {` ` ` `// Get the index of the current character` ` ` `var` `C = str[i].charCodeAt(0) - ` `'a'` `.charCodeAt(0);` ` ` `// If the current character has` ` ` `// appeared before in the string` ` ` `if` `(lastPos[C] != -1) {` ` ` `// Update the result` ` ` `res = Math.max(len - (i - lastPos[C] - 1) - 1, res);` ` ` `}` ` ` `// Update the last position` ` ` `// of the current character` ` ` `lastPos[C] = i;` ` ` `}` ` ` `return` `res;` `}` `// Driver code` `var` `str = ` `"geeksforgeeks"` `;` `var` `len = str.length;` `document.write( maxLength(str, len));` `</script>` |

**Output:**

12

**Time Complexity:** O(n) where n is the length of the input string.