This post is completed by 1 user

  • 0
 Add to List
Medium

373. Longest substring with at most two unique characters

Objective: Given a string, write an algorithm to find the longest substring with at most two characters.

Example:

Input: aabbccddc
Output: ccddc, length: 5

Input: aabacbeeeebeaabb
Output: beeeebe, length 7

Input: aaaaaa
Output: Only one unique character is present in the input string

Approach: Brute Force

Identify all the substrings of the given input string and check each substring with no of unique characters in it and pick the one with maximum length.

Time Complexity: O(N3), N^2 for all finding the substrings and O(N) for each substring while checking unique characters.

Better Solution - Linear Search 

  • Check if string has at least 2 unique characters if no then print the error message and return.
  • Let's say we take substring between indexes curr_start and curr_end, both points to index 0 at the beginning.
  • Keep adding one character at a time to the substring by moving curr_end pointer to the right and make sure that condition of substring has at most 2 unique characters at a time is valid by adding the new character and if any point the condition is not valid then start moving curr_start pointer to the right till condition is valid again.
  • At each step, keep track of length of maximum substring by doing curr_end-curr_start.  
  • To check whether substring has only 2 unique characters, maintain an array of size 26 ( 26 alphabets) and array with filled with the count of characters in the string to the respective index. 0th index for 'a' and 25th index for z.
  • See the example below for more understanding.

Time Complexity: O(N)

Input: aabcd
curr_start: 0, curr_end: 1, max_Start: 0, max_Length: 0
Processing character: a
SubString: a
a:1
curr_start: 0, curr_end: 1, max_Start: 0, max_Length: 1
-------------------------------------------------------------------
Processing character: a
SubString: aa
a:2
curr_start: 0, curr_end: 2, max_Start: 0, max_Length: 2
-------------------------------------------------------------------
Processing character: b
SubString: aab
a:2, b:1
curr_start: 0, curr_end: 3, max_Start: 0, max_Length: 3
-------------------------------------------------------------------
Processing character: c
SubString: aabc
a:2, b:1, c:1
More than 2 unique characters in substring, moving curr_start to right
curr_start: 1, curr_end: 4, max_Start: 0, max_Length: 3
a:1, b:1, c:1
More than 2 unique characters in substring, moving curr_start to right
curr_start: 2, curr_end: 4, max_Start: 0, max_Length: 3
b:1, c:1
curr_start: 2, curr_end: 4, max_Start: 0, max_Length: 3
-------------------------------------------------------------------
Processing character: d
SubString: bcd
b:1, c:1, d:1
More than 2 unique characters in substring, moving curr_start to right
curr_start: 3, curr_end: 5, max_Start: 0, max_Length: 3
c:1, d:1
curr_start: 3, curr_end: 5, max_Start: 0, max_Length: 3
--------------------------------------------------------------------
Longest substring with two most unique characters is : aab with length 3 (start index = max_Start=0 and length=max_Lenth=3)

Output:

Input: aabcd
Longest substring with two most unique characters is : aab with length 3
Input: aaaaa
Only one unique character is present in the input string

Related Problems: