Check if String Is Decomposable Into Value-Equal Substrings

Check if String Is Decomposable Into Value-Equal Substrings - Problem

String Easy

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.

Input & Output

Example 1 — Valid Decomposition

$ Input: s = "00111"

› Output: true

💡 Note: We can decompose "00111" into "00" (length 2) and "111" (length 3). Exactly one substring has length 2.

Example 2 — Invalid Decomposition

$ Input: s = "01111"

› Output: false

💡 Note: We cannot form value-equal substrings since '0' and '1' are different. Groups must contain identical characters.

Example 3 — Multiple Groups Invalid

$ Input: s = "000111"

› Output: false

💡 Note: Both "000" and "111" have length 3, so we have zero groups of length 2, but we need exactly one.

Constraints

1 ≤ s.length ≤ 1000
s consists only of digits

Visualization

Tap to expand

Understanding the Visualization

Input

String with consecutive identical characters

Group

Identify groups of consecutive identical characters

Validate

Check if exactly one group can contribute length-2 substring

Key Takeaway

🎯 Key Insight: Each group of identical characters must have length that is either divisible by 3 or leaves remainder 2, with exactly one group having remainder 2

Asked in

G Google 25 M Microsoft 18

The key insight is that each group of consecutive identical characters must have a length that leaves remainder 0 or 2 when divided by 3, and exactly one group must have remainder 2. Best approach is the optimized single-pass solution. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Decompositions	O(3^n)	O(n)	Generate all possible ways to split the string and check each one
Single Pass with Mathematical Check	O(n)	O(1)	Count consecutive groups and check if exactly one has remainder 2 when divided by 3

Brute Force - Try All Decompositions — Algorithm Steps

Find all consecutive groups of identical characters
Try all possible ways to split each group into lengths 2 and 3
Check if exactly one group contributes a length-2 substring

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Groups

Find consecutive identical characters

Try Combinations

For each group, try all ways to use 2s and 3s

Validate

Check if exactly one group uses a length-2 substring

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int* getGroups(const char* s, int* groupCount) {
    int* groups = (int*)malloc(strlen(s) * sizeof(int));
    *groupCount = 0;
    int i = 0;
    int len = strlen(s);
    
    while (i < len) {
        char ch = s[i];
        int count = 1;
        while (i + count < len && s[i + count] == ch) {
            count++;
        }
        groups[(*groupCount)++] = count;
        i += count;
    }
    return groups;
}

bool canDecompose(int* groups, int groupCount, int groupIdx, int usedTwo) {
    if (groupIdx == groupCount) {
        return usedTwo == 1;
    }
    
    int count = groups[groupIdx];
    
    for (int twos = 0; twos <= count / 2; twos++) {
        int remaining = count - 2 * twos;
        if (remaining % 3 == 0) {
            int newUsedTwo = usedTwo + (twos > 0 ? 1 : 0);
            if (newUsedTwo <= 1) {
                if (canDecompose(groups, groupCount, groupIdx + 1, newUsedTwo)) {
                    return true;
                }
            }
        }
    }
    return false;
}

bool solution(const char* s) {
    int groupCount;
    int* groups = getGroups(s, &groupCount);
    bool result = canDecompose(groups, groupCount, 0, 0);
    free(groups);
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3^n)

For each group of identical characters, we try all ways to split it using 2s and 3s

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth and space to store group information

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

487 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Decompositions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler