This post is completed by 1 user
|Add to List|
Longest contiguous character in a given String - O(N) Solution
Objective: Given an input string, write an algorithm to find the longest contiguous character or in other words, find a maximum consecutive character in the string.
Input: "aaabbccccddbbaaa" Output: c, count = 4 Input: "bbbbb" Output: b, count=5
Naive Approach: Use two nested loops
The outer loop to fix it on the current character and inner loop will count the occurrence of the current character. Keep track of the character which occurs maximum times consecutively.
Time Complexity: O(N^2)
Better Approach: Use Single Loop
- Put the pointer to first character. Iterate through the string.
- If the current character is the same as the previous character, increase the count. else reset the count = 1 for the current character.
- Keep track of the character which occurs maximum times consecutively and its count.
- See the code for more understanding.
Time Complexity: O(N)
Input: aaaabbaacccccde, Longest Contiguous Character: c with count: 5 Input: bbbbbbb, Longest Contiguous Character: b with count: 7 Input: abcdeaab, Longest Contiguous Character: a with count: 2