Largest Covering Substring
MediumStrings · Google
A substring of text covers required if, for every character, the substring contains that character at least as many times as required does. For example, "baca" covers "aab", but "bac" does not (it has only one a).
Return the lexicographically largest substring of text that covers required. If no substring covers it, return the empty string "".
Lexicographic order is ordinary string comparison: compare character by character, and if one string is a prefix of the other, the longer one is larger (so "cb" < "cba").
Example 1
- Input:
- required = "od", text = "codexdog"
- Output:
- "xdog"
- Explanation
- The last start whose remaining suffix still contains an
oand adis index 5 ("dog"), so only starts 0 to 5 can work. The largest letter there is thexat index 4, and the best substring starting atxis the whole rest of the text,"xdog".
Example 2
- Input:
- required = "bb", text = "abcbab"
- Output:
- "cbab"
- Explanation
- Two
bs are needed, and the last start whose suffix still has twobs is index 3. Among starts 0 to 3 the largest letter is thecat index 2, and extending to the end only makes the string larger, so the answer is"cbab".
Example 3
- Input:
- required = "q", text = "abc"
- Output:
- ""
- Explanation
qnever appears in the text, so no substring coversrequiredand the answer is the empty string.
Constraints
1 <= required.length <= 10^51 <= text.length <= 10^5- Both strings contain only lowercase English letters