EqualSubstrings
SRM 221 · 2004-12-01 · by AdminBrett
SRM 221 · 2004-12-01 · by AdminBrett · Brute Force
Problem Statement
Problem Statement
You will be given a String str consisting of lowercase letters. You will return a String[] containing elements x and y in that order. The returned String s x and y must satisfy:
- 1) The string xy (x with y concatenated on the end) must equal str.
- 2) The number of a's in x must equal the number of b's in y.
- 3) If multiple solutions are possible, use the one that maximizes the length of x.
Constraints
- str will contain between 1 and 50 characters inclusive.
- Each character in str will be a lowercase letter ('a'-'z').
Examples
0)
"aaabbb"
Returns: { "aaa", "bbb" }
Here we can split str right down the center.
1)
"bbbaaa"
Returns: { "bbb", "aaa" }
Again the center works.
2)
"bbbbbb"
Returns: { "bbbbbb", "" }
y can be empty.
3)
"aaaaaa"
Returns: { "", "aaaaaa" }
x can be empty.
4)
"abjlkbjalkbjaljsbljbalb"
Returns: { "abjlkbjalkbjaljs", "bljbalb" }
Make sure to maximize the length of x.
Submissions are judged against all 52 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EqualSubstrings with a public method vector<string> getSubstrings(string str) · 52 test cases · 2 s / 256 MB per case