This post is completed by 1 user

Add to List 
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_endcurr_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)
Code:
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
Also Read: