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.

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.

Description Hints 3 Solution Video 7:09

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

Q: 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.

Q: 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.

Easy50.4% acceptancePremium elsewhere, free here

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

Topics

String

Hints open one at a time

Hint 1

Keep looking for 3-equals, if you find a 3-equal, keep going. If you don't find a 3-equal, check if it is a 2-equal.

Hint 2

Make sure that it is the only 2-equal.

Hint 3

If it is neither a 3-equal nor a 2-equal, then it is impossible.

7:09

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"000111000"

Input

"00011111222"

Input

"011100022233"

Your code is saved on this device.Solution