*994*

A string is said to be valid when it has only distinct characters and none of them repeat simultaneously. For example, if string ‘s two distinct characters are

xandy, then valid examples could bexyxyxoryxyxybut notxxyyorxyyx.Question:Given a sample string, we need to determine what is the maximum length of valid string that can be made by deleting any of the characters.Input:beabeefeabOutput:5

##### Explanation:

Let us try to understand the output for the sample test case.

If we delete ** e** and

**, the resulting string is**

*f***. Hence, this is a valid as there are only two distinct characters (**

*babab***and**

*a***), and none of them repeat simultaneously. The length of this string is 5.**

*b*##### Brute Force Method:

To solve this problem let us first try to consider the brute force approach.

- Find all the distinct character in string
**beabeefeab**= {a, b, e, f} - For each possible pair of the distinct characters, form the resultant string. If it is valid find the length

Ex:**a,e**[String made = eaeeea] NOT VALID**a,f**[String made = afa] VALID [Length = 3]**b,f**[String made = bbfb] NOT VALID**a,b**[String made = babab] VALID [Length = 5] - Find the maximum lengths of all the possible combinations and print the maximum length.

This is the brute force approach to the problem and has a complexity of **O(n^3)**. The approach will fail if the length of the input string very long.

##### Optimized Approach:

Let us try to understand a O(n) approach for the problem.

Find all the distinct characters in the input string = **{a, b, e, f}**

Make a n x n matrix where n is the count of distinct characters.

| A | B | E | F |

A | ||||

B | ||||

E | ||||

F |

Parse each of the character in the string and start filling each of the row and column.

String: **beabeefeab**

##### For letter ‘*b*‘:

*b*

A | B | E | F | |

A | B | |||

B | B | B | B | B |

E | B | |||

F | B |

##### For letter **‘e’:**

If the cell is already filled, just cross it out and fill the new letter.

| A | B | E | F |

A | B | E | ||

B | B | B | B E | B |

E | E | B E | E | E |

F | B | E |

##### For letter ‘**a**‘:

| A | B | E | F |

A | A | B A | E A | A |

B | B A | B | B E | B |

E | E A | B E | E | E |

F | A | B | E |

##### For letter ‘**b**‘:

Notice that while filling ‘b’, b is uncrossed in cell (B-B) and (F-B) and (B-F). This means that we cannot have any of these combinations. As a result, we flag these cells.

| A | B | E | F |

A | A | B A B | E A | A |

B | B A B | B | B E B | B |

E | E A | B E B | E | E |

F | A | B | E |

##### For letter **‘e’:**

Again notice that (E-E), (F-E) and (E-F) cells already have an ‘e’. This means we cannot have these combinations and flag them.

| A | B | E | F |

A | A | B A B | E A E | A |

B | B A B | B | B E B E | B |

E | E A E | B E B E | E | E |

F | A | B | E |

##### For letter** ‘f’**:

| A | B | E | F |

A | A | B A B | E A E | A F |

B | B A B | B | B E B E | B F |

E | E A E | B E B E | E | E F |

F | A F | B F | E F | F |

##### For letter** ‘e’:**

‘e’ is already present in (A-E), (B-E), (E-E), (E-A), (E-B). Hence flag all these.

| A | B | E | F |

A | A | B A B | E A E | A F |

B | B A B | B | B E B E | B F |

E | E A E | B E B E | E | E F E |

F | A F | B F | E F E | F |

**For letter ‘a’**:

Looking at it, ‘a’ is already present in A-A. Hence flag it.

| A | B | E | F |

A | A | B A B A | E A E A | A F A |

B | B A B A | B | B E B E | B F |

E | E A E A | B E B E | E | E F E |

F | A F A | B F | E F E | F |

**For letter ‘b’: **

If you look at it, ‘b’ is already present in (B-B) but it is already flagged, so continue.

| A | B | E | F |

A | A | B A B A B | E A E A | A F A |

B | B A B A B | B | B E B E B | B F B |

E | E A E A | B E B E B | E | E F E |

F | A F A | B F B | E F E | F |

##### Evaluating Result:

Now we are finished parsing the string. See the un-flagged cells. We have the combinations. (A-B) and and (A-F) which can form valid strings. To get the maximum length iterate over each of the un-flagged cells and find the maximum length possible. This comes out to be 5.

To get the valid answer string itself, just see all the characters in the matrix in the cell with the maximum length. As a result, our maximum length valid string will be *babab*

##### Code:

Below is the JAVA code for the above approach. The solution below uses a 26 x 26 matrix but the general idea remains the same.

```
import java.util.Scanner;
/**
* Created by nikoo28 on 7/5/17.
*/
public class TwoCharacters {
public static final int NUM_LETTERS = 26;
public static void main(String[] args) {
/* Save input */
Scanner scan = new Scanner(System.in);
int length = scan.nextInt();
String str = scan.next();
scan.close();
/* Edge case */
if (length <= 1) {
System.out.println(0);
return;
}
/* Create arrays representing the 26^2 subproblems */
int[][] pair = new int[NUM_LETTERS][NUM_LETTERS];
int[][] count = new int[NUM_LETTERS][NUM_LETTERS];
for (int i = 0; i < length; i++) {
char letter = str.charAt(i);
int letterNum = letter - 'a';
/* Update row */
for (int col = 0; col < NUM_LETTERS; col++) {
if (pair[letterNum][col] == letter) {
count[letterNum][col] = -1;
}
if (count[letterNum][col] != -1) {
pair[letterNum][col] = letter;
count[letterNum][col]++;
}
}
/* Update column */
for (int row = 0; row < NUM_LETTERS; row++) {
if (pair[row][letterNum] == letter) {
count[row][letterNum] = -1;
}
if (count[row][letterNum] != -1) {
pair[row][letterNum] = letter;
count[row][letterNum]++;
}
}
}
/* Find max in "count" array */
int max = 0;
for (int row = 0; row < NUM_LETTERS; row++) {
for (int col = 0; col < NUM_LETTERS; col++) {
max = Math.max(max, count[row][col]);
}
}
System.out.println(max);
}
}
```

Code language: Java (java)

A working implementation of the above code can be found here.

You can also find the code and test cases on Github.

## 6 comments

Really appreciate the effort for explaining it simply.

I have a question, this algorithm using dynamic approach yields O(n^2) but not O(n). Please correct me if I’m wrong.

If you look at the loops closely, only the outer loop runs till the length(n) of string. The inner loop runs only of NUM_LETTERS = 26 times.

This will always happen in a constant time, and hence it will not increase exponentially if the length of the string increases.

note:-(F-F) can form valid string but it is marked in red invalid in table and in video it is correct

thank you for the correction. I made the edit. :)

Do we have to delete pair of characters ,we can’t delete more or less than two characters simultaneously ?

Hi Shantun,

I think I did not understand your concern correctly. Are you referring to the problem statement or my solution?

As per the solution we are just flagging which pair of characters can’t be a part of the final output.

Could you please elaborate if you still have a doubt?

Comments are closed.