Given string str, the task is to find the length of the longest substring of str such that no three consecutive characters in the substring are same.
Input: str = “baaabbabbb”
“aabbabb” is the required substring.
Input: str = “babba”
Given string itself is the longest substring.
Approach: The following steps can be followed to solve the problem:
- If the length of the given string is less than 3 then the length of the string will be the answer.
- Initialize temp and ans as 2 initially, since this is the minimum length of the longest substring when the length of the given string is greater than 2.
- Iterate in the string from 2 to N – 1 and increment temp by 1 if str[i] != str[i – 1] or str[i] != str[i – 2].
- Else re-initialize temp = 2 and ans = max(ans, temp).
Below is the implementation of the above approach:
Time Complexity: O(N) where N is the length of the string.
Space Complexity: O(1)
- Length of the longest substring with no consecutive same letters
- Longest substring of only 4's from the first N characters of the infinite string
- Length of the longest substring without repeating characters
- Print Longest substring without repeating characters
- Longest substring with K unique characters using Binary Search
- Find the longest substring with k unique characters in a given string
- Rearrange the characters of the string such that no two adjacent characters are consecutive English alphabets
- Minimum characters that are to be inserted such that no three consecutive characters are same
- Largest substring with same Characters
- Longest Common Substring | DP-29
- Longest substring with count of 1s more than 0s
- Longest Palindromic Substring | Set 1
- Longest Palindromic Substring | Set 2
- Longest substring of vowels
- Longest Non-palindromic substring
If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to firstname.lastname@example.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please Improve this article if you find anything incorrect by clicking on the "Improve Article" button below.