• 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 nn characters.

Output

Print one integer: the length of the longest repetition.

Constraints

  • 1≤n≤1061≤n≤106

Example

Input:
ATTCGGGA

Output:
3

JAVA Solution :-

import java.io.DataInputStream;

import java.io.FileInputStream;

import java.io.IOException;

import java.util.Arrays;

import java.util.HashMap;

class Main {

public static void main(String[] args) throws IOException {

Reader sc = new Reader();

String st = sc.readLine();

long max=1;

for(int i=0;i<st.length()-1;)

{

int count=1;

char ch = st.charAt(i);

for(int j=i+1;j<st.length();j++)

{

if(ch==st.charAt(j))

{

count++;

}

else{

break;

}

}

if(count>=max)

{

max=count;

}

i=i+count;

}

System.out.println(max);

// while(t →0)

// {

// solve(sc);

// }

}

public static void solve(Reader sc) throws IOException

{

}

static class Reader {

final private int BUFFER_SIZE = 1 << 16;

private DataInputStream din;

private byte[] buffer;

private int bufferPointer, bytesRead;

public Reader()

{

din = new DataInputStream(System.in);

buffer = new byte[BUFFER_SIZE];

bufferPointer = bytesRead = 0;

}

public Reader(String file_name) throws IOException

{

din = new DataInputStream(

new FileInputStream(file_name));

buffer = new byte[BUFFER_SIZE];

bufferPointer = bytesRead = 0;

}

public String readLine() throws IOException

{

byte[] buf = new byte[10000000]; // line length

int cnt = 0, c;

while ((c = read()) != -1) {

if (c == ‘\n’) {

if (cnt != 0) {

break;

}

else {

continue;

}

}

buf[cnt++] = (byte)c;

}

return new String(buf, 0, cnt);

}

public int nextInt() throws IOException

{

int ret = 0;

byte c = read();

while (c <= ‘ ‘) {

c = read();

}

boolean neg = (c == ‘-’);

if (neg)

c = read();

do {

ret = ret * 10 + c — ‘0’;

} while ((c = read()) >= ‘0’ && c <= ‘9’);

if (neg)

return -ret;

return ret;

}

public long nextLong() throws IOException

{

long ret = 0;

byte c = read();

while (c <= ‘ ‘)

c = read();

boolean neg = (c == ‘-’);

if (neg)

c = read();

do {

ret = ret * 10 + c — ‘0’;

} while ((c = read()) >= ‘0’ && c <= ‘9’);

if (neg)

return -ret;

return ret;

}

public double nextDouble() throws IOException

{

double ret = 0, div = 1;

byte c = read();

while (c <= ‘ ‘)

c = read();

boolean neg = (c == ‘-’);

if (neg)

c = read();

do {

ret = ret * 10 + c — ‘0’;

} while ((c = read()) >= ‘0’ && c <= ‘9’);

if (c == ‘.’) {

while ((c = read()) >= ‘0’ && c <= ‘9’) {

ret += (c — ‘0’) / (div *= 10);

}

}

if (neg)

return -ret;

return ret;

}

private void fillBuffer() throws IOException

{

bytesRead = din.read(buffer, bufferPointer = 0,

BUFFER_SIZE);

if (bytesRead == -1)

buffer[0] = -1;

}

private byte read() throws IOException

{

if (bufferPointer == bytesRead)

fillBuffer();

return buffer[bufferPointer++];

}

public void close() throws IOException

{

if (din == null)

return;

din.close();

}

}

}

Learn Like Noob