EqualSubstrings2
SRM 683 · 2016-01-04 · by Arterm
Problem Statement
You are given a
(The two substrings must be non-empty. Each substring must be contiguous.)
Constraints
- s will consist only of lowercase English letters ('a'-'z').
- The length of s will be between 1 and 50, inclusive.
"aa" Returns: 1
There is exactly one way how to choose two non-empty and non-overlapping substrings. In this case they happen to be equal (both are "a"), so the correct return value is 1.
"abcd" Returns: 0
Regardless how we choose two non-overlapping substrings, they will always differ.
"aba" Returns: 1
One pair: ("a", "a").
"abab" Returns: 3
Three pairs: ("a", "a"), ("b", "b"), ("ab", "ab").
"aaaab" Returns: 7
The 7 ways to select the two equal substrings are shown below. Each row represents one way. The characters 1 and 2 denote characters selected to form the first and second substring, respectively. aaaab ----- 12... 1.2.. 1..2. .12.. .1.2. ..12. 1122. (In the first six ways, the two selected substrings are "a" and "a". In the last way the selected substrings are "aa" and "aa".)
Submissions are judged against all 43 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EqualSubstrings2 with a public method int get(string s) · 43 test cases · 2 s / 256 MB per case