# 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)

**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