PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
A string of odd length is called cute if it has either o or u at each odd index and w at each even index.
Given a string S, find the length of its longest contiguous substring that’s cute.
EXPLANATION:
Checking if the substring of S from index L to index R is cute can be done easily:
- Check if (R-L+1) is odd, since cute strings must have odd length.
- Check if S_L, S_{L+2}, S_{L+4}, \ldots, S_R are each either
ooru. - Check if S_{L+1}, S_{L+3}, \ldots, S_{R-1} are all equal to
w.
We can then apply this check to each pair (L, R) such that 1 \le L \le R \le N.
Across all pairs that pass the check, record and print the maximum value of (R-L+1).
This algorithm takes \mathcal{O}(N^3) time if implemented directly, which is fast enough for the given constraints.
TIME COMPLEXITY:
\mathcal{O}(N^3) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = input()
ans = 0
for i in range(n):
cute = True
for j in range(i, n):
if i%2 == j%2:
if s[j] not in 'ou': cute = False
if cute: ans = max(ans, j-i+1)
else:
if s[j] != 'w': cute = False
print(ans)