We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if String Is Decomposable Into Value-Equal Substrings

Number: 2070

Difficulty: Easy

Paid? Yes

Companies: N/A

Problem Description

Given a digit string s, determine whether it is possible to break s into a sequence of consecutive substrings – each substring being a “value‐equal” string (i.e. all characters in it are the same) – such that exactly one of these substrings has length 2 and all the remaining substrings have length 3.

Key Insights

  • The only allowed substring lengths are 2 and 3.
  • You are allowed to partition even a maximal group (of consecutive identical digits) into multiple valid substrings.
  • For any contiguous segment (a group) of identical digits of length L, the segment can be split into pieces of size 2 and 3 if and only if there exists nonnegative integers k and r such that 2k + 3r = L.
  • The total count of pieces of length 2 across all groups must be exactly one.
  • Use dynamic programming to combine the possibilities from individual groups to verify if a global partition meeting the criteria exists.

Space and Time Complexity

Time Complexity: O(n * L) in worst case, where n is the number of groups and L is the length of a group (in the worst-case scenario L can be O(n)); overall O(N^2) for input length N.
Space Complexity: O(n) for the DP state and additional storage for group counts.

Solution

We first break the input string into maximal groups of consecutive equal digits. For each group of length L, we determine all possible ways to partition it into pieces of lengths 2 and 3. Each way can be represented by the count of pieces that are of length 2 in that group. For instance, if L = 5 there is one possibility: one piece of length 2 and one piece of length 3 (because 2+3 = 5).
Once the possibilities for each group are known (as counts of “2-length” pieces), we use dynamic programming to combine these possibilities over all groups and check if it is possible to achieve exactly one piece of length 2 overall.
The DP works as follows:

  1. Initialize a DP set (or boolean array) with a starting count of 0.
  2. For each group, for every previously possible overall count, add each possible count that can come from splitting the current group.
  3. In the end, check if the value 1 is reachable.

This algorithm uses grouping and a knapSack–style DP to combine choices across groups.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def isDecomposable(self, s: str) -> bool:
        # Step 1: Split s into groups of consecutive identical digits.
        groups = []
        count = 1
        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                count += 1
            else:
                groups.append(count)
                count = 1
        groups.append(count)  # add the last group

        # dp will store possible total number of 2-length segments so far.
        dp = {0}
        
        # Process each group
        for group_length in groups:
            possible_twos = set()
            # For current group, try all possible splits using k pieces of length 2.
            # k must be in range 0 to group_length//2
            for k in range(group_length // 2 + 1):
                remainder = group_length - 2 * k
                # Check if the remaining length can be exactly partitioned into pieces of length 3.
                if remainder % 3 == 0:
                    possible_twos.add(k)
            # If no valid split for current group, then answer is false.
            if not possible_twos:
                return False
            
            # Combine current group's possibilities with previous DP state.
            new_dp = set()
            for prev_twos in dp:
                for curr_twos in possible_twos:
                    new_dp.add(prev_twos + curr_twos)
            dp = new_dp
        
        # Final condition: exactly one piece of length 2 must be obtained.
        return 1 in dp

# Example Usage:
# sol = Solution()
# print(sol.isDecomposable("00011111222")) # Expected output: True
← Back to All Questions