LeetCode 1933 - Check if String Is Decomposable Into Value-Equal Substrings

LeetCode Problem 1933

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to determine if a given string s, consisting solely of digits '0' through '9', can be split into consecutive value-equal substrings such that exactly one substring has length 2 and all remaining substrings have length 3. A value-equal substring is a sequence of identical characters, like "111" or "22".

The input is a single string s with length between 1 and 1000. The output is a boolean: true if s can be decomposed according to the rules, and false otherwise.

Key observations from the constraints:

Every character belongs to some substring.
Substrings can only have lengths 2 or 3, and only one substring may have length 2.
The string is short (≤ 1000 characters), so a linear or near-linear algorithm is feasible.

Edge cases include strings that:

Have length less than 2 (impossible to form a substring of length 2 or 3).
Have all identical characters but lengths that do not fit the decomposition rules.
Have mixed-length value-equal segments that cannot satisfy the "exactly one length-2" constraint.

Approaches

A brute-force approach would try every possible way to split the string into value-equal substrings of length 2 or 3. For each segment of identical characters, we could try to form substrings of length 2 and 3 in all combinations while ensuring that exactly one length-2 substring exists. While correct, this method would have exponential time complexity because each segment could branch into multiple combinations.

The optimal approach relies on the insight that for each contiguous segment of identical characters, the decomposition into length-2 and length-3 substrings can be decided greedily:

If a segment length is divisible by 3, we take all substrings of length 3.
If a segment length modulo 3 equals 2, we can take one length-2 substring and the rest of length 3.
If a segment length modulo 3 equals 1, it is impossible to decompose according to the rules.

We also track whether we have already used a length-2 substring, because the rule allows exactly one length-2 substring in total. If any segment cannot be decomposed, we immediately return false.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Tries all splits of value-equal segments into lengths 2 and 3, exponential branching.
Optimal	O(n)	O(1)	Greedily process contiguous segments, track single length-2 substring usage.

Algorithm Walkthrough

Initialize a variable used_length2 to False to track whether the unique length-2 substring has been used.
Iterate over the string to identify contiguous segments of identical characters.
For each segment, calculate its length seg_len.
If seg_len % 3 == 0, the segment can be split entirely into substrings of length 3.
If seg_len % 3 == 2, check if used_length2 is already True. If it is, return false. Otherwise, mark used_length2 = True.
If seg_len % 3 == 1, the segment cannot be decomposed into valid substrings, so return false.
After processing all segments, return True if all segments have been decomposed and exactly one length-2 substring has been used.

Why it works: Each segment of identical characters is independent. The modulo 3 logic guarantees that a valid decomposition exists if and only if the segment lengths can be split into lengths 3 and exactly one length-2 substring. Tracking used_length2 ensures the "exactly one" constraint.

Python Solution

class Solution:
    def isDecomposable(self, s: str) -> bool:
        n = len(s)
        i = 0
        used_length2 = False
        
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            seg_len = j - i
            
            if seg_len % 3 == 0:
                pass  # all length-3 substrings
            elif seg_len % 3 == 2:
                if used_length2:
                    return False
                used_length2 = True
            else:  # seg_len % 3 == 1
                return False
            
            i = j
        
        return True

Implementation Walkthrough: We iterate over the string with a pointer i. For each segment of repeated characters, we compute the segment length. Using modulo 3, we decide whether the segment can be decomposed. We track the use of a single length-2 substring to enforce the problem's constraint. If any segment cannot fit the rules, we immediately return False.

Go Solution

func isDecomposable(s string) bool {
    n := len(s)
    i := 0
    usedLength2 := false

    for i < n {
        j := i
        for j < n && s[j] == s[i] {
            j++
        }
        segLen := j - i

        if segLen % 3 == 0 {
            // all length-3 substrings
        } else if segLen % 3 == 2 {
            if usedLength2 {
                return false
            }
            usedLength2 = true
        } else {
            return false
        }
        i = j
    }

    return true
}

Go Differences: The Go version uses zero-based indexing and explicit loops instead of Python's slicing. There is no need to worry about nil strings, and boolean handling is straightforward.

Worked Examples

Example 1: "000111000"

i	segment	seg_len	used_length2	Decision
0	"000"	3	False	OK
3	"111"	3	False	OK
6	"000"	3	False	OK

All segments processed, used_length2 is still False. Not exactly one length-2 substring → False.

Example 2: "00011111222"

i	segment	seg_len	seg_len % 3	used_length2	Decision
0	"000"	3	0	False	OK
3	"11111"	5	2	False	Use length-2 → True
8	"222"	3	0	True	OK

All segments processed, exactly one length-2 substring → True.

Example 3: "011100022233"

i	segment	seg_len	seg_len % 3	used_length2	Decision
0	"0"	1	1	False	Cannot decompose → `False`

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the string, processing each character once.
Space	O(1)	Constant extra space used to track the single length-2 substring and pointers.

The algorithm is efficient for the input size constraints and does not require additional data structures beyond a few variables.

Test Cases

sol = Solution()

# Provided examples
assert sol.isDecomposable("000111000") == False  # no length-2 substring
assert sol.isDecomposable("00011111222") == True  # valid decomposition
assert sol.isDecomposable("011100022233") == False  # segment of length 1 at start

# Edge cases
assert sol.isDecomposable("11") == True  # single length-2 substring
assert sol.isDecomposable("111") == False  # only length-3, but no length-2
assert sol.isDecomposable("111222") == False  # all length-3, no length-2
assert sol.isDecomposable("11111222") == True  # one length-2 substring from "11111"
assert sol.isDecomposable("11111222333") == True  # one length-2 substring

# Stress cases
assert sol.isDecomposable("0"*1000) == False  # all length-3 segments, no length-2
assert sol.isDecomposable("0"*998 + "00") == True  # exactly one length-2 substring at end

Test	Why
"000111000"	Ensures algorithm rejects strings without length-2 substring
"00011111222"	Valid decomposition with one length-2 substring
"011100022233"	Segment too short at start → invalid
"11"	Smallest valid string with only length-2 substring
"111"	Only length-3 substring, no length-2 → invalid
"11111222"	One length-2 substring embedded in larger segment
"0"*998 + "00"	Stress test with large input, valid decomposition at end