1933. Check if String Is Decomposable Into Value-Equal Substrings π
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 <= 1000
s
consists 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)$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|