Watch 3 video solutions for Check if String Is Decomposable Into Value-Equal Substrings, a easy level problem involving String. This walkthrough by Software Interviews Prep has 82 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A value-equal string is a string where all characters are the same.
"1111" and "33" are value-equal strings."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 <= 1000s consists of only digits '0' through '9'.Problem Overview: You are given a numeric string s. The goal is to split it into substrings where every substring contains the same digit. All substrings must have length 3 except for exactly one substring which must have length 2. Return true if such a decomposition is possible.
Approach 1: Brute Force Group Simulation (O(n) time, O(1) space)
Start by scanning the string and identifying contiguous groups of the same digit. For each group of length k, try to simulate splitting it into chunks of size 3 and possibly one chunk of size 2. Groups with k % 3 == 1 immediately make the decomposition impossible because you would be left with a substring of length 1. Track how many groups require a size‑2 substring (k % 3 == 2). If more than one group requires it, the rule of "exactly one length‑2 substring" is violated. This approach relies purely on scanning runs of characters in the string.
Approach 2: Two Pointers Run-Length Scan (O(n) time, O(1) space)
Use a two pointers technique to compute run lengths of identical digits. One pointer marks the start of a group, and the second pointer advances while the characters are equal. Once a run ends, compute its length len = right - left. If len % 3 == 1, decomposition is impossible because neither 3-length nor 2-length pieces can cover that remainder. If len % 3 == 2, this run must supply the single allowed substring of length 2. Track how many times this happens. After scanning the entire string, return true only if exactly one run produced remainder 2.
The key insight: valid decompositions consist of blocks of size 3 plus exactly one block of size 2. A run length modulo analysis reveals whether a run can be composed from these sizes without leaving invalid fragments.
Recommended for interviews: The two pointers run-length scan is the expected solution. It processes the string once, keeps constant memory, and directly validates the mathematical constraints on group sizes. Explaining why len % 3 == 1 fails and why exactly one len % 3 == 2 is required shows strong reasoning about string grouping and modular arithmetic.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Group Simulation | O(n) | O(1) | Useful for reasoning about valid group sizes and understanding the decomposition rules. |
| Two Pointers Run-Length Scan | O(n) | O(1) | Best approach for production or interviews. Single pass through the string with constant memory. |