1933. Check if String Is Decomposable Into Value-Equal Substrings
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
falsesince 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
trueif 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.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Solution 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:
iwhich points to the beginning of the current group of identical characters.jwhich 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 returnsfalse. -
If the length of the group modulo 3 is
2, we've potentially found our one substring of length 2. We increment thecnt2counter to mark this occurrence. Ifcnt2becomes greater than1, it means we've found more than one such group, which violates the problem rules, and thus the function returnsfalse. -
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.
How does merge sort divide the problem into subproblems?
Example Walkthrough
Let's walk through a small example using the string s = "22255577766" to illustrate the solution approach.
- Initialize
ito 0, because that is where we'll start our search for consecutive character groups. - Initialize a counter
cnt2to 0, which will keep track of groups of length 2.
We start our first loop:
- Set
j = i, and in this casej = 0, since we are at the start of the string. - Increment
jas long ass[j]is equal tos[i]. The characters at index 0, 1, and 2 are all "2", sojwill increment through these indices. - When
jreaches 3,s[j]is no longer equal tos[i], so we've found our first group "222". The length of this group isj - 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:
iis now 3, and we restart the process withj = i. We incrementjas "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 = 6andj = 9. The length is 3, modulo 3 is 0, which is fine. - We now encounter "66" with
i = 9andj = 11. The length isj - i = 11 - 9 = 2. - The length 2 modulo 3 is 2, so we have found a potential group of length 2. We increment
cnt2to 1.
Since we have reached the end of the string, we now check:
cnt2equals 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
331class 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}
401class 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};
441/**
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}
43Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
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.
Which of the following array represent a max heap?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.