RepeatStringEasy
SRM 698 (Google) · 2016-08-27 · by cgy4ever
SRM 698 (Google) · 2016-08-27 · by cgy4ever · Dynamic Programming
Problem Statement
Problem Statement
A string S is called a square if there is some string T such that S = T + T.
For example, the strings "", aabaab" and "xxxx" are squares, but "a", "aabb" and "aabbaa" are not.
You are given aString s.
Find the longest square string that can be obtained from s by erasing some (possibly none, possibly all) of its characters.
In other words, we are looking for the longest square that occurs in s as a subsequence.
Return the length of that square.
Note that the answer is well-defined, as the square "" (the empty string) will always occur in s as a subsequence.
You are given a
Note that the answer is well-defined, as the square "" (the empty string) will always occur in s as a subsequence.
Constraints
- s will contain between 1 and 50 characters, inclusive.
- Each character in s will be a lowercase English letter ('a'-'z').
Examples
0)
"frankfurt" Returns: 4
The longest square that occurs in "frankfurt" is "frfr". Its length is 4.
1)
"single" Returns: 0
The letters in the string "single" are all distinct. Hence, the only square that occurs in this string is "". The length of this square is zero.
2)
"singing" Returns: 6
3)
"aababbababbabbbbabbabb" Returns: 18
4)
"x" Returns: 0
Submissions are judged against all 143 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RepeatStringEasy with a public method int maximalLength(string s) · 143 test cases · 2 s / 256 MB per case