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)\).

Python3JavaC++GoTypeScript

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

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;
    }
};

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;
}

Comments