DSA sheet / Introductory
Repetitions
The problem in brief
You get a string of the letters A, C, G and T, up to a million characters long. Print the length of the longest stretch of one repeated letter.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1069.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Any single left-to-right pass can only remember a few numbers. What is the smallest amount of state that lets you know how long the current stretch is?
-
When you look at a character, there are only two cases: it equals the previous one, or it does not. What should the running length do in each?
-
Where does the answer live? It is not the final running length, it is the best running length you have ever seen.
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
The brute force would compare every substring with a “all characters equal” check, which is O(n^2) or worse and hopeless at a million characters. The way out is to notice that runs never overlap: each character belongs to exactly one maximal run, so a single pass that tracks “the run I am in” already visits every run once.
The transferable habit: when a question is about a contiguous block with a local property, keep a small state describing the block ending at the current position (its length, its sum, its min), update it in O(1) per element, and keep a separate variable for the best value so far. You will meet the same shape in maximum subarray sum.
Intuition
Walk along the string with a finger. If the next letter matches, the run grows by one. If it does not, the run restarts at length one. Every time the run grows, check if it beat your record.
Approach
- Set best = 1 and current = 1 (the string has at least one character).
- For each position i from 1 to n - 1: if s[i] == s[i - 1], current += 1, else current = 1.
- After each step do best = max(best, current).
- Print best.
Edge cases: a single character (answer 1); a string of all one letter (answer n); a string with no repeats (answer 1). Read the string as a whole line, not with a per-character function that would be slow.
Complexity
O(n) time, O(1) extra memory beyond the input string.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int best = 1, cur = 1;
for (size_t i = 1; i < s.size(); i++) {
cur = (s[i] == s[i - 1]) ? cur + 1 : 1;
best = max(best, cur);
}
cout << best << "\n";
return 0;
}import sys
def main():
s = sys.stdin.readline().strip()
best = cur = 1
for i in range(1, len(s)):
cur = cur + 1 if s[i] == s[i - 1] else 1
if cur > best:
best = cur
print(best)
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String s = in.readLine().trim();
int best = 1, cur = 1;
for (int i = 1; i < s.length(); i++) {
cur = (s.charAt(i) == s.charAt(i - 1)) ? cur + 1 : 1;
best = Math.max(best, cur);
}
System.out.println(best);
}
}const s = require('fs').readFileSync(0, 'utf8').trim();
let best = 1;
let cur = 1;
for (let i = 1; i < s.length; i++) {
cur = s[i] === s[i - 1] ? cur + 1 : 1;
if (cur > best) best = cur;
}
console.log(best);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).