[HackerRank] – Two Characters

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 x and y, then valid examples could be xyxyx or yxyxy but not xxyy or xyyx.

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: beabeefeab
Output: 5

Explanation:

Let us try to understand the output for the sample test case.
If we delete e and f, the resulting string is babab. Hence, this is a valid as there are only two distinct characters (a and b), and none of them repeat simultaneously. The length of this string is 5.

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‘:

	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.

Video Explanation: