Check if String Is Decomposable Into Value-Equal Substrings

Problem

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 of2 and the remaining substrings have a length of3.

Return true if you can decomposes according to the above rules. Otherwise, returnfalse.

A substring is a contiguous sequence of characters in a string.

Examples

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'.

Solution

Method 1 – Greedy Grouping

Intuition

We want to split the string into value-equal substrings, with exactly one of length 2 and the rest of length 3. The greedy approach is to always take groups of 3 when possible, and use a group of 2 only once when necessary.

Reasoning

By grouping as many 3-length substrings as possible, we minimize the number of 2-length substrings. If at any point we need more than one 2-length group, or if a group of length 1 remains, the decomposition is not possible. This works because the only allowed group sizes are 2 (once) and 3 (any number of times).

Approach

1. Initialize a counter for the number of 2-length groups used (start at 0).
2. Iterate through the string, grouping consecutive equal characters.
3. For each group of length cnt:
   • While cnt >= 3, take away groups of 3.
   • If cnt == 2, increment the 2-length group counter.
   • If cnt == 1, return false (cannot form a group of 1).
4. At the end, return true if exactly one 2-length group was used, else false.

Edge cases:

• String length less than 2: always false.
• More than one group of length 2: false.

Code

C++

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

Go

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

Java

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

Kotlin

class Solution {
    fun isDecomposable(s: String): Boolean {
        var i = 0
        var two = 0
        while (i < s.length) {
            var j = i
            while (j < s.length && s[j] == s[i]) j++
            var len = j - i
            while (len >= 3) len -= 3
            if (len == 2) two++
            else if (len == 1) return false
            i = j
        }
        return two == 1
    }
}

Python

class Solution:
    def is_decomposable(self, s: str) -> bool:
        n, two = len(s), 0
        i = 0
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            l = j - i
            while l >= 3:
                l -= 3
            if l == 2:
                two += 1
            elif l == 1:
                return False
            i = j
        return two == 1

Rust

impl Solution {
    pub fn is_decomposable(s: String) -> bool {
        let n = s.len();
        let s = s.as_bytes();
        let mut i = 0;
        let mut two = 0;
        while i < n {
            let mut j = i;
            while j < n && s[j] == s[i] {
                j += 1;
            }
            let mut l = j - i;
            while l >= 3 {
                l -= 3;
            }
            if l == 2 {
                two += 1;
            } else if l == 1 {
                return false;
            }
            i = j;
        }
        two == 1
    }
}

Complexity

• ⏰ Time complexity: O(n), as we scan the string once and process each group in constant time.
• 🧺 Space complexity: O(1), as we use only a few variables for counting and indices.