1003. Check If Word Is Valid After Substitutions

MediumStackString
Leetcode Link

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:

  1. We iterate through each character of the string s.
  2. 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".
  3. 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 string t, and we can remove this sequence from the stack.
  4. We repeat the above steps until we have processed the entire string s.
  5. At the end, if the string s is valid (meaning composed only of "abc" substrings), our stack t 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

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?

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:

  1. 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 with if len(s) % 3: which returns False if the condition is met.

  2. Initialization of the Stack: A Python list named t is used here as the stack. This list will store characters from the input string.

  3. Iterating through String s:

    • The algorithm iterates through every character c in the string s.
    • Each character is appended to the top of the stack t.

  4. 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:] = [].

  5. 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 of True.
    • 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 string s is not valid and False 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.

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

Which algorithm should you use to find a node that is close to the root of the tree?

Example 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".

  1. Length Check: Our string s has a length of 6, which is divisible by 3. This passes our first check.

  2. Initialization of the Stack: We initialize an empty stack t.

  3. Iterating through String s: We process characters of s 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'].

  4. 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".

  5. 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".

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
Not Sure What to Study? Take the 2-min Quiz：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Recommended Readings

Stack Intro

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 - Top Patterns for Coding Interviews

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 Review

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

←
↑TA 👨‍🏫