# 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)$.

• class Solution {
public boolean isDecomposable(String s) {
int i = 0, n = s.length();
int cnt2 = 0;
while (i < n) {
int j = i;
while (j < n && s.charAt(j) == s.charAt(i)) {
++j;
}
if ((j - i) % 3 == 1) {
return false;
}
if ((j - i) % 3 == 2 && ++cnt2 > 1) {
return false;
}
i = j;
}
return cnt2 == 1;
}
}

• class Solution {
public:
bool isDecomposable(string s) {
int cnt2 = 0;
for (int i = 0, n = s.size(); i < n;) {
int j = i;
while (j < n && s[j] == s[i]) {
++j;
}
if ((j - i) % 3 == 1) {
return false;
}
cnt2 += (j - i) % 3 == 2;
if (cnt2 > 1) {
return false;
}
i = j;
}
return cnt2 == 1;
}
};

• class Solution:
def isDecomposable(self, s: str) -> bool:
i, n = 0, len(s)
cnt2 = 0
while i < n:
j = i
while j < n and s[j] == s[i]:
j += 1
if (j - i) % 3 == 1:
return False
cnt2 += (j - i) % 3 == 2
if cnt2 > 1:
return False
i = j
return cnt2 == 1


• func isDecomposable(s string) bool {
i, n := 0, len(s)
cnt2 := 0
for i < n {
j := i
for j < n && s[j] == s[i] {
j++
}
if (j-i)%3 == 1 {
return false
}
if (j-i)%3 == 2 {
cnt2++
if cnt2 > 1 {
return false
}
}
i = j
}
return cnt2 == 1
}

• function isDecomposable(s: string): boolean {
const n = s.length;
let cnt2 = 0;
for (let i = 0; i < n; ) {
let j = i;
while (j < n && s[j] === s[i]) {
++j;
}
if ((j - i) % 3 === 1) {
return false;
}
if ((j - i) % 3 === 2 && ++cnt2 > 1) {
return false;
}
i = j;
}
return cnt2 === 1;
}