GoodSubstrings
Rookie SRM 9 · 2022-01-21 · by praveen123
Problem Statement
You are given a string s consisting of lower case English letters and '.'. A string is called good if all of its characters are equal, e.g. "aaa" is good whereas "aab" is not.
Each '.' should be replaced by a letter ('a' - 'z') so as to maximize number of good substrings in s. Return the maximum number of possible good substrings you can have.
Constraints
- Number of characters in s will be between 1 and 500, inclusive.
- Each character of s will be a lower case English letter ('a' to 'z') or '.'.
"aab" Returns: 4
Following 4 substrings are good. Assume 1 based indexing. s[1, 1] = "a", s[1, 2] = "aa", s[2, 2] = "a", s[3, 3] = "b".
"a." Returns: 3
You can fill '.' by 'a' and get string "aa" whose all three substrings are good.
"enjoy..the..problem" Returns: 25
"topcoder.is.quite...good..imho...." Returns: 56
".acb.a.cbcac..b.b..bb.caaacbac.abcab..bbababcb.aa." Returns: 119
Submissions are judged against all 220 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GoodSubstrings with a public method int maxGoodSubstrings(string s) · 220 test cases · 2 s / 256 MB per case