Repetitions

Problem Statement -

• Time limit: 1.00 s

• Memory limit: 512 MB

You are given a DNA sequence: a string consisting of characters A, C, G, and T. Your task is to find the longest repetition in the sequence. This is a maximum-length substring containing only one type of character.

Input

The only input line contains a string of n characters.

Output

Print one integer: the length of the longest repetition.

Constraints

• 1 ≤ n ≤ 10^6

Example

Input:

ATTCGGGA

Output:

3

LOGIC

To solve this problem, we keep track of the most frequent letter. Let’s say a letter ‘x’ has most frequency initially. Now, if another letter ‘y’ has greater frequency we’ll change our answer to frequency of ‘y’.

APPROACH

We take a string ‘s’ as input and run a while loop until we reach its end. Inside the while loop, we have another while loop to indicate that while the next character is identical to current and we’ve not reached the end of string keep incrementing the frequency. When while loop breaks(i.e. next character is not same as the current), save the frequency in an array index equivalent to array[char-‘0’] provided that there’s not a greater frequency already saved at this index. To understand this better, suppose that “AATAAA” is string ’s’. Now, firstly in frequency array, at index [’A’-‘0’], the value will be 1(We are not counting initial A here, later answer will be printed as answer+1 to get final answer). Later, value at same index will be updated to 2 when encountering 3 A’s. In the end, we print answer as frequency as frequency+1 as the frequency values stored in array are one less than the actual value due to the fact that we are not counting the initial character.

CODE

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
int main()
{
    ll i=0, max = INT_MIN, cnt[150] = {0};
    string s;
    cin >> s;
    while(s[i] != '\0')
    {
        ll c = 0;
        while(s[i] == s[i+1] && s[i] != '\0'){
			c++;
			i++;
        }
        if(c > cnt[s[i] - '0'])
	    cnt[s[i] - '0'] = c;
	i++;
    }
    for(ll i=0; i<150; i++)
        if(cnt[i] > max)
	    max = cnt[i];
    cout << max+1 << endl; 
    return 0;
}