1003. Check If Word Is Valid After Substitutions
Problem Description
This problem presents a string manipulation task where you are given a string s
and need to determine if it can be considered "valid" based on a specific operation. In this context, a valid string is one that can be formed by repeatedly inserting the substring "abc"
at any position within an initially empty string t
. Therefore, you can imagine starting with nothing and each time inserting "abc" somewhere into the string you're building until it matches the string s
provided.
To put it simply, you are to verify if string s
can be entirely composed of the substring "abc"
repeated multiple times, possibly interspersed within each other but always in the correct order.
Intuition
The approach to solving this problem is nicely suited to a stack data structure because stacks are good at checking for patterns that should emerge in the reverse order in which they are read. Each time an "abc"
pattern is detected within the string s
, it is as if we can remove that pattern because it could represent one of the inserts that we previously made while constructing it.
Here's the intuition step-by-step:
- We iterate through each character of the string
s
. - We add each character to a stack
t
. The use of a stack allows us to monitor the most recent characters that have been added and see if they form the sequence"abc"
. - After adding each character, we check if the last three characters of the stack
t
are"abc"
. If they are, it means we have found a valid sequence that could have been inserted into our initially empty stringt
, and we can remove this sequence from the stack. - We repeat the above steps until we have processed the entire string
s
. - At the end, if the string
s
is valid (meaning composed only of"abc"
substrings), our stackt
should be empty because every"abc"
sequence would have been removed as it was detected.
The solution leverages the fact that if an "abc"
pattern is found at any point, it can be eliminated as it represents a valid sequence that builds up the string s
. If at the end there are characters left in the stack that cannot form the string "abc"
, then the initial string s
could not have been formed exclusively by inserting "abc"
, and therefore it is not valid.
Learn more about Stack patterns.
Solution Approach
The solution to this problem makes use of a simple but efficient data structure - the stack. A stack follows a Last In, First Out (LIFO) principle, which means that the last element added is the first one to be removed. This is perfect for the problem at hand, where we need to continuously check the last few elements for a specific pattern ("abc"
).
Let's walk through the implementation as outlined in the reference solution:
-
Length Check: Right off the bat, the solution employs a quick check to see if the length of the input string
s
is divisible by 3. If it’s not, the input can't possibly be a valid string since the patter"abc"
is 3 characters long. This is executed withif len(s) % 3:
which returnsFalse
if the condition is met. -
Initialization of the Stack: A Python list named
t
is used here as the stack. This list will store characters from the input string. -
Iterating through String
s
:- The algorithm iterates through every character
c
in the strings
. - Each character is appended to the top of the stack
t
.
- The algorithm iterates through every character
-
Pattern Detection and Removal:
- After each character is added, the solution checks if the stack’s size is at least 3 and if the top three elements form the string
"abc"
. - If they do, it means that a valid sequence has been found, and it removes the top three elements from the stack. The check and removal is succinctly performed by
if ''.join(t[-3:]) == 'abc': t[-3:] = []
.
- After each character is added, the solution checks if the stack’s size is at least 3 and if the top three elements form the string
-
Final Check:
- After the iteration is complete, there's one final check to see whether the stack is empty.
- If the stack is empty, this indicates that all elements of the string
s
formed valid sequences of"abc"
and were removed during the iteration, which means the input string is valid. This results in a return value ofTrue
. - If there are any elements left on the stack, then there are characters which did not form the pattern
"abc"
correctly. As such, the input strings
is not valid andFalse
is returned.
In conclusion, this approach cleverly uses a stack to keep track of and identify valid patterns ("abc"
) through iteration and pattern matching which when found, are removed, simulating the building process described in the problem statement.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example where the string s
is "aabbcc"
. We need to determine if this string can be constructed by repeatedly inserting the substring "abc"
.
-
Length Check: Our string
s
has a length of 6, which is divisible by 3. This passes our first check. -
Initialization of the Stack: We initialize an empty stack
t
. -
Iterating through String
s
: We process characters ofs
one by one:- We insert 'a' into stack
t
. - Now our stack
t
looks like['a']
. - Next, we insert 'a' again.
- Now our stack
t
looks like['a', 'a']
. - We insert 'b'.
- Now our stack
t
looks like['a', 'a', 'b']
. - We insert another 'b'.
- Now our stack
t
looks like['a', 'a', 'b', 'b']
. - We insert 'c'.
- Now our stack
t
looks like['a', 'a', 'b', 'b', 'c']
. - Finally, we insert another 'c'.
- Now our stack
t
looks like['a', 'a', 'b', 'b', 'c', 'c']
.
- We insert 'a' into stack
-
Pattern Detection and Removal:
- We observe that after adding each character, we don't find a sequence
"abc"
at the top of the stack at any point during this process. The stack never reaches a point where the top three elements are"abc"
.
- We observe that after adding each character, we don't find a sequence
-
Final Check:
- After processing all characters, we find that the stack
t
is full of characters and contains['a', 'a', 'b', 'b', 'c', 'c']
. - Clearly, these cannot form the required
"abc"
pattern and hence cannot be removed. - Since our stack is not empty, the string
s
cannot be formed solely by inserting the substring"abc"
.
- After processing all characters, we find that the stack
In this example, the final stack not being empty indicates that the input string "aabbcc"
is not valid based on our criteria. Therefore, the function would return False
.
Solution Implementation
1class Solution:
2 def isValid(self, s: str) -> bool:
3 # Early check to ensure the length of the string is a multiple of 3
4 if len(s) % 3:
5 return False
6
7 # Initialize an empty list that will simulate a stack
8 stack = []
9
10 # Iterate over each character in the string
11 for char in s:
12 # Add the current character to the stack
13 stack.append(char)
14
15 # Check if the last 3 characters in the stack form the string 'abc'
16 if ''.join(stack[-3:]) == 'abc':
17 # If they do, pop the last 3 characters from the stack
18 stack[-3:] = []
19
20 # If the stack is empty after processing the entire string, return True
21 # This indicates that the string was composed entirely of 'abc' sequences
22 return not stack
23
1class Solution {
2
3 /**
4 * Checks if the input string is valid by applying the following rule recursively:
5 * if the string contains the substring "abc", it removes this substring and continues.
6 * The string is valid if it can be reduced to an empty string using this rule.
7 *
8 * @param s The input string to be validated.
9 * @return true if the string is valid, false otherwise.
10 */
11 public boolean isValid(String s) {
12 // If the length of the string is not a multiple of 3, it cannot be valid
13 if (s.length() % 3 != 0) {
14 return false;
15 }
16
17 // Using StringBuilder for efficient modification of the string
18 StringBuilder stringBuilder = new StringBuilder();
19
20 // Iterate over the characters of the input string
21 for (char character : s.toCharArray()) {
22 // Append the current character to the stringBuilder
23 stringBuilder.append(character);
24
25 // Check if the last 3 characters form the substring "abc"
26 if (stringBuilder.length() >= 3 && "abc".equals(stringBuilder.substring(stringBuilder.length() - 3))) {
27 // If we found "abc", delete it from the stringBuilder
28 stringBuilder.delete(stringBuilder.length() - 3, stringBuilder.length());
29 }
30 }
31
32 // If stringBuilder is empty, all occurrences of "abc" have been removed and the string is valid
33 return stringBuilder.length() == 0;
34 }
35}
36
1class Solution {
2public:
3 // Function to check if a given string is valid, following specified constraints
4 bool isValid(string s) {
5 // Return false if the string length is not a multiple of 3
6 if (s.size() % 3 != 0) {
7 return false;
8 }
9
10 // Use a variable `temp` to store the intermediate string states
11 string temp;
12
13 // Iterate over each character in the input string
14 for (char c : s) {
15 // Append the current character to `temp`
16 temp.push_back(c);
17
18 // Check if the last three characters in `temp` form the string "abc"
19 if (temp.size() >= 3 && temp.substr(temp.size() - 3, 3) == "abc") {
20 // If "abc" is found, erase the last three characters from `temp`
21 temp.erase(temp.end() - 3, temp.end());
22 }
23 }
24
25 // If `temp` is empty, all occurrences of "abc" have been resolved; return true
26 // If `temp` is not empty, the string is invalid; return false
27 return temp.empty();
28 }
29};
30
1// Function to check if the given string can be fully reduced by successive removal of substring "abc"
2function isValid(s: string): boolean {
3 // If the string length is not a multiple of 3, it can't be fully reduced
4 if (s.length % 3 !== 0) {
5 return false;
6 }
7
8 // Temporary stack to hold characters for processing
9 const tempStack: string[] = [];
10
11 // Iterate over each character in the string
12 for (const char of s) {
13 // Push the current character onto the temp stack
14 tempStack.push(char);
15
16 // Check if the top 3 elements of the stack form the substring "abc"
17 if (tempStack.slice(-3).join('') === 'abc') {
18 // If they do, pop these 3 characters off the stack
19 tempStack.splice(-3);
20 }
21 }
22
23 // If the temp stack is empty, then the string is valid and can be fully reduced
24 return tempStack.length === 0;
25}
26
Time and Space Complexity
The provided Python code defines a method isValid
which takes a string s
as input and returns a boolean indicating whether the input string can be reduced to an empty string by repeatedly deleting the substring "abc"
.
Time Complexity
The time complexity of the function is O(n)
where n
is the length of the input string s
. This is because the function iterates through each character of the string exactly once, and the inner check—if the last three characters form the substring "abc"
—is done in constant time, as it involves only a fixed-size (i.e., 3 characters) comparison and slice assignment. Therefore, the iteration dominates the runtime, resulting in a linear complexity relative to the length of the string.
Space Complexity
The space complexity of the function is also O(n)
, as it potentially stores all characters of the string in the list t
if the input does not contain any "abc"
substrings to remove. In the worst-case scenario, where the string s
is made up entirely of characters none of which combine to form "abc"
, the list t
will grow to the same size as the string s
. Therefore, the space used by the list t
scales linearly with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.