378. 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.

Example:

Input: "aaabbccccddbbaaa"
Output: c, count = 4

Input: "bbbbb"
Output: b, count=5

Approach:

Naive Approach: 

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)

Output:

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

Related Problems:

- Largest word in dictionary by removing a few characters from the given string Beginner
- Reverse a String using Recursion Beginner
- Compare two version numbers of a software Medium
- Valid Multiple Parentheses Medium
- Valid or Well Formed Parentheses | Part - 1 Medium