Longest Substring with At Most Two Distinct Characters

Moderate
0/80
profile
Contributed by
10 upvotes
Asked in companies
Flipkart limitedUKG (Ultimate Kronos Group)

Problem statement

You are given a string ‘S’, you need to find the length of the longest substring that contains at most two distinct characters.

Note:

A string ‘B’ is a substring of a string ‘A’ if ‘B’ that can be obtained by deletion of, several characters(possibly none) from the start of ‘A’ and several characters(possibly none) from the end of ‘A’.
Follow up : 
Can you try to solve this problem in O(N) time and O(1) space.
Example : 
If ‘S’ = “ninninja”

Then, “ninnin” is the longest substring that contains at most two distinct characters. We will print the length of this substring which is equal to 6.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a string ‘S’, denoting the input string.
Output Format : 
For each test case, print the length of the longest substring containing at most two distinct characters.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 10      
1 ≤ |S| ≤ 1000
Where 'S' contains lowercase English alphabets

Time limit: 1 sec
Sample Input 1 :
2
ninninja
aaa
Sample Output 1 :
6
3
Explanation For Sample Input 1 :
For test case 1 :
We will print 6 because:
“ninnin” is the longest substring containing at most two distinct characters.

For test case 2 : 
We will print 3 because:
The given string “aaa” itself contains a single character, therefore the longest substring will itself be “aaa”.
Sample Input 2 :
2
ninjacoder
abbadca
Sample Output 2 :
3
4
Hint

Try to generate all the substrings and check which satisfies the given condition and select the string which gives the maximum length.

Approaches (2)
Brute Force

A standard brute force approach is to generate all the substrings, this takes ~O(N^2) time, then for each of the substring, we will check how many distinct characters it contains, therefore the total time complexity turns out to be of the order ~O(N^3).

 

We can further optimise the above approach by generating substrings starting that start from a particular index (let’s say ‘i’) and stopping the search when the number of characters is greater than two, we will require an additional data structure like a hash-set to keep a track of distinct characters for the substrings starting from index ‘i’. We can repeat this process for all the indices, and return the final answer.

 

The steps are as follows :

  1. Initialize a variable ‘ans’ equal to 0, this will store the length of the longest substring.
  2. Run a for loop for variable ‘i’ from 0 to N - 1, inside the loop:
    • Declare a hash-set ‘distinctChars’, to store the distinct characters in the substrings starting from the index ‘st’.
    • Run an inner for loop for variable ‘j’ from i to N - 1, for each iteration:
      • Insert the character at s[j] in the hash-set, if the size of the hash-set is less than 2, then continue the process, else: update the value of ‘ans’ if needed and break the inner loop.
  3. Finally, return the value stored in ‘ans’.
Time Complexity

O( N ^ 2 ), where N denotes the length of the string.

 

In the worst-case, when there are at most two distinct characters in the string itself, we will be iterating through all the ~N^2 substrings possible.

Hence the time complexity is O( N^2 ).

Space Complexity

O( 1 )

 

No extra space is used, the hash-set used contains a maximum of two to three characters at max.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Longest Substring with At Most Two Distinct Characters
Full screen
Console