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;
}

Recent Posts

See All

Increasing Array

Problem Statement - Time limit: 1.00 s Memory limit: 512 MB You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the

Missing Number

Problem Statement - Time limit: 1.00 s Memory limit: 512 MB You are given all numbers between1,2,…,n except one. Your task is to find the missing number. Input The first input line contains an integer

Weird Algorithm

Problem Statement - Time limit: 1.00 s Memory limit: 512 MB Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorith

©2019 by EduGeekX. Proudly created with Wix.com