Skip to main content
Talentd

Check if String Is Decomposable Into Value-Equal Substrings - Solution & Explanation

EasyPremiumFree on FleetCodeString7 min read
Practice this problem

Problem Statement

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

Approach Overview

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.

Solution

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Group SimulationO(n)O(1)Useful for reasoning about valid group sizes and understanding the decomposition rules.
Two Pointers Run-Length ScanO(n)O(1)Best approach for production or interviews. Single pass through the string with constant memory.

Video Solution

Leetcode | Easy | 1933. Check if String Is Decomposable Into Value-Equal Substrings | Javascript • Software Interviews Prep • 88 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Check if String Is Decomposable Into Value-Equal Substrings easy or hard?
LeetCode classifies this problem as Easy. The main challenge is recognizing that run lengths must follow the pattern 3k or 3k+2, with exactly one 3k+2 run. Once that observation is made, the implementation becomes a straightforward O(n) scan.
Check if String Is Decomposable Into Value-Equal Substrings Python/Java solution
Implement a single pass over the string while counting consecutive equal digits. When a run ends, compute its length and evaluate the remainder when divided by 3. Track how many runs have remainder 2 and ensure none have remainder 1. This logic translates directly into Python, Java, C++, Go, and TypeScript implementations.
How to solve Check if String Is Decomposable Into Value-Equal Substrings in O(n)?
Scan the string and measure the length of each contiguous block of equal digits. For each length k, check k % 3. If the remainder is 1, return false. Count how many blocks have remainder 2. After processing all runs, return true only if exactly one block produced remainder 2. This guarantees one substring of length 2 and the rest length 3.
What is the best approach for Check if String Is Decomposable Into Value-Equal Substrings?
The optimal approach is a two pointers run-length scan. Iterate through the string and compute lengths of consecutive identical digits. If any run length has remainder 1 when divided by 3, decomposition is impossible. Exactly one run must have remainder 2 so it can form the single substring of length 2. This solution runs in O(n) time and O(1) space.
Is Check if String Is Decomposable Into Value-Equal Substrings asked at Google/Amazon/Meta?
Problems involving string grouping, run-length encoding, and modular constraints are common in interviews at companies like Google, Amazon, and Meta. While this exact question may not always appear, the technique of scanning runs and validating group sizes frequently shows up in string processing interview questions.
What data structure is used in Check if String Is Decomposable Into Value-Equal Substrings?
The solution primarily uses string traversal with two pointers. No additional data structures such as hash maps or stacks are required because the algorithm only tracks the current run length and a counter for runs that require a length‑2 substring.
What is the time complexity of Check if String Is Decomposable Into Value-Equal Substrings?
The optimal solution runs in O(n) time because the string is scanned once while counting consecutive identical characters. Space complexity is O(1) since only a few counters and pointers are stored regardless of input size.

Ready to solve this problem?

Practice Check if String Is Decomposable Into Value-Equal Substrings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring