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

EasyString

Problem Description

In this problem, we are given a string s that consists only of digits. The task is to figure out if we can split the string into multiple substrings where each substring consists of identical characters (value-equal string), and follows a specific pattern: all but one of these substrings must have a length of 3, and exactly one substring should have a length of 2.

For instance, the string "55566777" can be split into "555", "66", and "777". As you can see, all substrings are value-equal, one substring is of length 2, and the others are of length 3. Therefore, the function should return true.

On the other hand, if we have a string like "55567777", it cannot be split into the required pattern of substrings since after splitting into "555", "6", and "777", "77", we are left with an extra "77" of length 2 which breaks the rule of having exactly one substring of length 2.

The function should return true if such a decomposition is possible, or false otherwise.

Intuition

The intuition behind the solution is to iterate through the string and count the length of consecutive characters that are the same. For every such group, we can immediately identify if the length of the group is incompatible with our rules (i.e., if the length mod 3 equals 1, we cannot make valid substrings out of it). If the group's length mod 3 equals 2, it means we have our candidate for the value-equal substring of length 2.

A few key points to notice here:

If we encounter more than one group where the length mod 3 equals 2, we must return false since we can only have one such substring.
If all groups have lengths that are multiples of 3, we do not have our required substring of length 2, and the answer should be false.
We only return true if we have exactly one group with a length mod 3 equals 2 and all other groups are multiples of 3.

The solution approach leverages these insights and uses two pointers, i and j, where i marks the start of a new consecutive group and j finds the end of this group. We keep track of whether we have found a substring of length 2 using the cnt2 variable. If we finish scanning the string and cnt2 is exactly 1, we can safely return true, indicating that the string s can be decomposed according to the given rules.

Solution Approach

The solution follows a straightforward approach to solve the problem iteratively without using any complex data structures or algorithms.

Starting point i is initialized at the start of the string. Then, the algorithm enters a loop that continues as long as i is less than the length of the string n.

Inside the loop, we use two pointers:

i which points to the beginning of the current group of identical characters.
j which finds the end of the group.

j is initialized to the same value as i and then increments as long as the next character in the string is equal to s[i], representing the same value-equal character group.

Once the end of the group is identified, we calculate the length of the group by subtracting i from j. We use this length to determine if the group contributes to the pattern we're looking for.

The remainders after division by 3 lead to three cases:

If the length of the group modulo 3 is 1, this means the group cannot be decomposed to meet the problem's requirements (since we would either need one extra character to make two substrings of length 3 or have one character left over after making one substring of length 3), so the function returns false.
If the length of the group modulo 3 is 2, we've potentially found our one substring of length 2. We increment the cnt2 counter to mark this occurrence. If cnt2 becomes greater than 1, it means we've found more than one such group, which violates the problem rules, and thus the function returns false.
If the length of the group modulo 3 is 0, it perfectly fits into the pattern as one or multiple substrings of length 3, and we don't need to do anything.

After processing the group, i is set to j to start examining the next group of identical characters.

Once we've finished scanning the string, the function checks if exactly one group of length 2 was found by checking if cnt2 is equal to 1. If true, we know that the string can be decomposed according to the given rules, and the function returns true. Otherwise, the function returns false.

This is an efficient approach since it scans the string only once, making the time complexity O(n), where n is the length of the string, and uses constant extra space.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example using the string s = "22255577766" to illustrate the solution approach.

Initialize i to 0, because that is where we'll start our search for consecutive character groups.
Initialize a counter cnt2 to 0, which will keep track of groups of length 2.

We start our first loop:

Set j = i, and in this case j = 0, since we are at the start of the string.
Increment j as long as s[j] is equal to s[i]. The characters at index 0, 1, and 2 are all "2", so j will increment through these indices.
When j reaches 3, s[j] is no longer equal to s[i], so we've found our first group "222". The length of this group is j - i = 3 - 0 = 3.
The length 3 modulo 3 is 0, so this group perfectly fits as a substring of length 3.

We update i = j and move to the next group:

i is now 3, and we restart the process with j = i. We increment j as "5" is consistent till index 5.
At j = 6, s[j] is not "5" anymore, so our group is "555". The length is 3, and modulo 3 is 0 again, fitting perfectly.

Continue this process:

For the next group "777", i = 6 and j = 9. The length is 3, modulo 3 is 0, which is fine.
We now encounter "66" with i = 9 and j = 11. The length is j - i = 11 - 9 = 2.
The length 2 modulo 3 is 2, so we have found a potential group of length 2. We increment cnt2 to 1.

Since we have reached the end of the string, we now check:

cnt2 equals 1, which is good, because we need exactly one group of length 2.

Since all other groups were of length 3 and we found exactly one group of length 2, the function would return true, indicating that the string s can be decomposed according to the given rules.

Solution Implementation

1class Solution:
2    def isDecomposable(self, s: str) -> bool:
3        index, length = 0, len(s)  # Initialize starting index and get the length of the string
4        count_of_twos = 0  # Counter for sequences with a length that leaves a remainder of 2 when divided by 3
5      
6        # Iterate through the string
7        while index < length:
8            current_char_index = index  # Start index of the current character sequence
9          
10            # Find the index where the current character sequence ends
11            while current_char_index < length and s[current_char_index] == s[index]:
12                current_char_index += 1
13
14            # Length of the current sequence
15            sequence_length = current_char_index - index
16          
17            # If the sequence is not divisible by 3 and leaves remainder 1, it's not decomposable
18            if sequence_length % 3 == 1:
19                return False
20
21            # If there is a sequence with a length that leaves a remainder of 2, increment the count
22            count_of_twos += sequence_length % 3 == 2
23          
24            # There should not be more than one sequence with a length that leaves a remainder of 2
25            if count_of_twos > 1:
26                return False
27
28            # Move to the next sequence
29            index = current_char_index
30      
31        # The string is decomposable if we find exactly one sequence with a remainder of 2
32        return count_of_twos == 1
33

1class Solution {
2    public boolean isDecomposable(String s) {
3        int startIndex = 0; // Initialize the start index of a sequence of same characters
4        int strLength = s.length(); // The total length of the string
5        int singlePairCount = 0; // Count of sequences where there are two characters (a pair)
6
7        // Iterate over the entire string to check each sequence
8        while (startIndex < strLength) {
9            int endIndex = startIndex;
10
11            // Find the end index until which the characters are the same
12            while (endIndex < strLength && s.charAt(endIndex) == s.charAt(startIndex)) {
13                endIndex++;
14            }
15
16            int sequenceLength = endIndex - startIndex; // Length of the current sequence
17
18            // If the sequence length divided by 3 leaves a remainder of 1, then it's not decomposable
19            if (sequenceLength % 3 == 1) {
20                return false;
21            }
22
23            // If the sequence length divided by 3 leaves a remainder of 2, increment the singlePairCount
24            // And if there is more than one such pair, it's not decomposable
25            if (sequenceLength % 3 == 2) {
26                singlePairCount++;
27                if (singlePairCount > 1) {
28                    return false; // More than one pair found, thus not decomposable
29                }
30            }
31
32            // Move to the next sequence
33            startIndex = endIndex;
34        }
35
36        // The string is decomposable if there is exactly one single pair of characters
37        return singlePairCount == 1;
38    }
39}
40

1class Solution {
2public:
3    bool isDecomposable(string s) {
4        // Initialize the starting index 'start', get the length of the string 'length',
5        // and a counter for sequences of length 2 ('twoCount').
6        int start = 0;
7        int length = s.size();
8        int twoCount = 0;
9      
10        // Iterate over the string.
11        while (start < length) {
12            // Initialize 'end' to find the end of the current sequence of the same characters.
13            int end = start;
14            // Increment 'end' while we have the same character as at the start of this sequence.
15            while (end < length && s[end] == s[start]) {
16                ++end;
17            }
18          
19            int sequenceLength = end - start;
20          
21            // If any sequence of characters is not divisible by 3 with a remainder of 0 or 2,
22            // it means the string cannot be decomposed as required.
23            if (sequenceLength % 3 == 1) {
24                return false;
25            }
26          
27            // If the remainder is 2 and we have already found a sequence of such type,
28            // return false because we can only have one sequence with a remainder of 2.
29            if (sequenceLength % 3 == 2) {
30                twoCount++; // Record that we found a two-character sequence
31                if (twoCount > 1) {
32                    return false; // If more than one such sequence is found, return false.
33                }
34            }
35          
36            // Move the start to the beginning of the next sequence.
37            start = end;
38        }
39      
40        // Check if there was exactly one sequence with a length that is a multiple of 3 plus 2.
41        return twoCount == 1;
42    }
43};
44

1/**
2 * Checks if the given string can be decomposed into a sequence of strings with each substring being a consecutive sequence of the same character, 
3 * and exactly one of these substrings is of length 2 (all others must be of length 3).
4 * @param {string} s - The input string to be checked for decomposability.
5 * @returns {boolean} - Returns true if the string can be decomposed as required, otherwise false.
6 */
7function isDecomposable(s: string): boolean {
8    let startIndex = 0;
9    const length = s.length;
10    let twoCount = 0;
11
12    // Iterate through the string.
13    while (startIndex < length) {
14        // Find the end index of the current sequence of the same characters.
15        let endIndex = startIndex;
16        while (endIndex < length && s.charAt(endIndex) === s.charAt(startIndex)) {
17            endIndex++;
18        }
19
20        const sequenceLength = endIndex - startIndex;
21      
22        // Check if any sequence of characters has a length not decomposable with a remainder of 0 or 2.
23        if (sequenceLength % 3 === 1) {
24            return false;
25        }
26      
27        // Track sequences of length 2 (remainder of 2 when divided by 3).
28        if (sequenceLength % 3 === 2) {
29            twoCount++;
30            // Having more than one sequence of this type makes it non-decomposable.
31            if (twoCount > 1) {
32                return false;
33            }
34        }
35      
36        // Move to the next sequence.
37        startIndex = endIndex;
38    }
39
40    // Ensure there was exactly one sequence of length 2.
41    return twoCount === 1;
42}
43

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the length of the input string s. This is because the while loop iterates over each character in the string exactly once, with i advancing to j at the end of each iteration. Even though there is a nested while loop, it only serves to increase j to the next character that is different from s[i], and each character is visited only once by this inner loop. Therefore, the overall number of operations is linear with respect to the size of the input string.

Space Complexity

The space complexity of the given code is O(1). This is due to the fact that the additional memory used does not depend on the input size; only a fixed number of variables are used (i, j, n, and cnt2). There are no data structures utilized that grow with the input size, which means the space used remains constant regardless of the length of s.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know