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)

Code:

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)

Code:

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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: