CSES: Repetitions Solution

Problem Statement

Problem Statement Link: CSES 1069: Missing Number Solution Link

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

Solution

# Import the sys module for standard input operations
import sys

# Function to read space-separated integers and return them as a list
def linput():
    return list(minput())

# Function to read space-separated integers from standard input and return as a map object
def minput():
    return map(int, sys.stdin.readline().strip().split())

# Read the input DNA sequence as a string
n = input()

# Initialize variables to keep track of the longest repetition (ans) and the current repetition (cur)
ans = 1
cur = 1

# Iterate through the characters of the input string starting from the second character
for i in range(1, len(n)):
    # Check if the current character is the same as the previous one
    if n[i] == n[i - 1]:
        # If yes, increment the current repetition length
        cur += 1
    else:
        # If not, update ans with the maximum of its current value and cur
        # and reset cur to 1, starting a new potential repetition
        ans = max(ans, cur)
        cur = 1

# Print the maximum of ans and cur
print(max(ans, cur))

Explanation

Certainly, let’s break down the logic of the solution step by step:

1. Initialization:

   ans = 1
   cur = 1

Initialize two variables, ans and cur, both set to 1. These variables will be used to keep track of the length of the longest repetition and the length of the current repetition, respectively.

2. Iteration through the DNA sequence:

   for i in range(1, len(n)):
       if n[i] == n[i - 1]:
           cur += 1
       else:
           ans = max(ans, cur)
           cur = 1

Iterate through the DNA sequence starting from the second character (index 1). For each character at position i, check if it is the same as the previous character (n[i - 1]). If it is, increment the cur variable, indicating that the current repetition continues. If the current character is different from the previous one, it means the current repetition has ended. In this case:

• Update ans with the maximum of its current value and the value of cur. This ensures that ans always stores the length of the longest repetition encountered so far.
• Reset cur to 1, starting a new potential repetition.

1. Handling the last repetition:

   print(max(ans, cur))

After the loop, print the maximum of ans and cur. This is necessary because the last repetition might be the longest, and we need to consider it after the loop.

4. Final Result:
   The final result printed is the length of the longest repetition in the given DNA sequence.

In summary, the logic of the solution revolves around iterating through the DNA sequence, keeping track of the current repetition length (cur), and updating the longest repetition length (ans) whenever a new repetition starts. The maximum repetition length is printed at the end, ensuring that the last repetition is considered.

You can find more blogs here.