Description
A value-equal string is a string where all characters are the same.
- For example,
"1111"and"33"are value-equal strings. - In contrast,
"123"is not a value-equal string.
Given a digit string s, decompose the string into some number of consecutive value-equal substrings where exactly one substring has a length of 2 and the remaining substrings have a length of 3.
Return true if you can decompose s according to the above rules. Otherwise, return false.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: s = "000111000" Output: false Explanation: s cannot be decomposed according to the rules because ["000", "111", "000"] does not have a substring of length 2.
Example 2:
Input: s = "00011111222" Output: true Explanation: s can be decomposed into ["000", "111", "11", "222"].
Example 3:
Input: s = "011100022233" Output: false Explanation: s cannot be decomposed according to the rules because of the first '0'.
Constraints:
1 <= s.length <= 1000sconsists of only digits'0'through'9'.
Solutions
Solution 1: Two Pointers
We traverse the string s, using two pointers i and j to count the length of each equal substring. If the length modulo 3 is 1, it means that the length of this substring does not meet the requirements, so we return false. If the length modulo 3 is 2, it means that a substring of length 2 has appeared. If a substring of length 2 has appeared before, return false, otherwise assign the value of j to i and continue to traverse.
After the traversal, check whether a substring of length 2 has appeared. If not, return false, otherwise return true.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
class Solution: def isDecomposable(self, s: str) -> bool: cnt2 = 0 for _, g in groupby(s): m = len(list(g)) if m % 3 == 1: return False cnt2 += m % 3 == 2 if cnt2 > 1: return False return cnt2 == 1(code-box)
