Home Strings [HackerRank] – Two Characters

[HackerRank] – Two Characters

by nikoo28
2 comments

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.

 ABEF
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‘:
 ABEF
A B  
BBBBB
E B  
F B  
For letter ‘e’:

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

 ABEF
A BE 
BBBB EB
EEB EEE
F BE 
For letter ‘a‘:
 ABEF
AAB AE AA
BB ABB EB
EE AB EEE
FABE 
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.

 ABEF
AAB A BE AA
BB A BBB E BB
EE AB E BEE
FABE 
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.

 ABEF
AAB A BE A EA
BB A BBB E B EB
EE A EB E B EEE
FABE 
For letter ‘f’:
 ABEF
AAB A BE A EA F
BB A BBB E B EB F
EE A EB E B EEE F
FA FB FE FF
For letter ‘e’:

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

 ABEF
AAB A BE A EA F
BB A BBB E B EB F
EE A EB E B EEE F E
FA FB FE F EF
For letter ‘a’:

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

 ABEF
AAB A B AE A E AA F A
BB A B ABB E B EB F
EE A E AB E B EEE F E
FA F AB FE F EF
For letter ‘b’:

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

 ABEF
AAB A B A BE A E AA F A
BB A B A BBB E B E BB F B
EE A E AB E B E BEE F E
FA F AB F BE F EF
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); } }


A working implementation of the above code can be found here.
You can also find the code and test cases on Github.

Video Explanation:

2 comments

You may also like

2 comments

Shantun Rubal July 7, 2017 - 17:36

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

Reply
nikoo28 July 8, 2017 - 01:58

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?

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More