Minimum Times To Append String For Subsequence
Given two strings s and t, determine the minimum number of times s must be repeated so that t becomes a subsequence of the repeated string.
Repeating s means appending complete copies of s one after another. If it is not possible to make t a subsequence of any repeated version of s, return -1.
Class RepeatedStringSubsequenceFinder
Method
Minimum Times To Append
int minimumTimesToAppend(String s, String t)
- Returns the minimum number of complete copies of
s required so that t is a subsequence of the final repeated string.
- Returns
0 if t is empty.
- Returns
-1 if at least one character of t does not appear in s.
Subsequence Definition
A string t is a subsequence of another string if t can be formed by deleting zero or more characters without changing the order of the remaining characters.
Constraints
1 ≤ s.length() ≤ 100,0000 ≤ t.length() ≤ 100,000s contains only lowercase English letters.t contains only lowercase English letters.
Examples
Example 1
minimumTimesToAppend(s = "abc", t = "cab")
Output: 2
Explanation: After repeating s two times, the string becomes "abcabc". The string "cab" is a subsequence of "abcabc".
Example 2
minimumTimesToAppend(s = "ab", t = "baab")
Output: 3
Explanation: After repeating s three times, the string becomes "ababab". The string "baab" is a subsequence of "ababab".
Example 3
minimumTimesToAppend(s = "abc", t = "acdbc")
Output: -1
Explanation: The character 'd' appears in t but not in s, so it is impossible.
Example 4
minimumTimesToAppend(s = "xyz", t = "")
Output: 0
Explanation: An empty string is already a subsequence, so no copy of s is required.