MagicalStringDiv1
SRM 609 · 2013-12-22 · by semiexp
SRM 609 · 2013-12-22 · by semiexp · Greedy, Simple Search, Iteration
Problem Statement
Problem Statement
Magical Girl Illy uses "magical strings" to cast spells.
For her, a string X is magical if and only if there exists a non-negative integer k such that X is composed of k consecutive '>' characters followed by k consecutive '<' characters.
Note that the empty string is also magical (for k=0).
Once Illy picked up aString S.
Each character of S was either '<' or '>'.
Illy can change S by removing some of its characters.
(The characters she does not remove will remain in their original order.)
Illy wants to change S into a magical string by removing as few of its characters as possible.
You are given theString S.
Compute and return the length of the magical string Illy will obtain from S.
Once Illy picked up a
You are given the
Constraints
- S will contain between 1 and 50 characters, inclusive.
- Each character of S will be '<' or '>'.
Examples
0)
"<><><<>" Returns: 4
The longest magical string Illy can produce is ">><<". Its length is 4. To change S into ">><<", Illy must remove the characters at 0-based indices 0, 2, and 6.
1)
">>><<<" Returns: 6
S is already a magical string. Therefore Illy doesn't have to remove any character.
2)
"<<<>>>" Returns: 0
Illy has to remove all characters of S.
3)
"<<<<><>>><>>><>><>><>>><<<<>><>>>>><<>>>>><><<<<>>" Returns: 24
4)
"<" Returns: 0
Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MagicalStringDiv1 with a public method int getLongest(string S) · 69 test cases · 2 s / 256 MB per case