This post is completed by 1 user

  • 0
Add to List
Beginner

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