Check If Word Is Valid After Substitutions - Leetcode Solution

Problem Statement:

You are given a string s that contains only lowercase English letters. A "word" refers to any substring of s that is an anagram of some permutation of the 26 lowercase English letters.

Return true if s is a valid word string, otherwise, return false.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "abccba" Output: true Explanation: The substrings that are a valid word are:

• "a" (1 times)
• "b" (2 times)
• "c" (2 times)
• "cc" (2 times)
• "bcc" (1 time)
• "abc" (1 time)
• "bca" (1 time)
• "cba" (1 time)
• "a" (1 times) Therefore, s is a valid word string.

Example 2:

Input: s = "abcd" Output: false Explanation: No substring of s is an anagram of some permutation of the 26 lowercase English letters.

Solution:

To solve this problem we first need to find out if a given substring is an anagram of some permutation of the 26 lowercase English letters. We can implement this using two approaches:

Approach 1:

We can use a hash map to store the frequency of each character in the substring. We then check if the frequency of each character in the substring is equal to the frequency of that character in some permutation of the 26 lowercase English letters (which is 1).

Approach 2:

We can use an array of size 26 to represent the frequency of each character in the substring. We then check if the frequency of each character in the substring is equal to the frequency of that character in some permutation of the 26 lowercase English letters (which is 1).

Now, we can use any of the above approaches to find out if a given substring is an anagram of some permutation of the 26 lowercase English letters.

Next, we need to find all possible substrings of the given string s. We can do this as follows:

We consider all possible pairs of indices i and j, such that i <= j. We then consider the substring s[i:j+1] and check if it is an anagram of some permutation of the 26 lowercase English letters.

If we find at least one substring that is an anagram of some permutation of the 26 lowercase English letters, then the given string s is a valid word string, otherwise, it is not.

Here is the Python code to implement the above solution:

def isValidWord(s: str) -> bool: n = len(s) if n % 3: return False stack = [] for c in s: stack.append(c) if len(stack) >= 3 and stack[-3:] == list("abc"): stack.pop() stack.pop() stack.pop() return not stack

s = "abcabcababcc" print(isValidWord(s))

Output:

True

Time Complexity:

The time complexity of the above solution is O(n^2), where n is the length of the given string s. This is because we are considering all possible pairs of indices i and j, where i <= j, to form all possible substrings of s. For each substring, we are checking if it is an anagram of some permutation of the 26 lowercase English letters, which takes O(k) time, where k is the length of the substring. Since the worst case value of k is n, the time complexity of checking all substrings is O(n^3). However, since the length of the given string s is at most 3000, the above solution works well within the given time limit.

1class Solution {
2public:
3    bool isValid(string S) {
4        
5        //Create a stack to store opening brackets
6        stack<char> opening;
7        
8        //Traverse through the string
9        for(int i = 0; i < S.length(); i++) {
10            
11            //If we encounter an opening bracket, push it onto the stack
12            if(S[i] == 'a' || S[i] == 'b' || S[i] == 'c')
13                opening.push(S[i]);
14            
15            //If we encounter a closing bracket
16            else {
17                
18                //If the stack is empty or the top element of the stack is not the corresponding opening bracket, return false
19                if(opening.empty() || (S[i] == 'b' && opening.top() != 'a') || (S[i] == 'c' && opening.top() != 'b'))
20                    return false;
21                
22                //If the stack is not empty and the top element of the stack is the corresponding opening bracket, pop the element from the stack
23                else
24                    opening.pop();
25            }
26        }
27        
28        //If the stack is empty at the end, return true
29        return opening.empty();
30    }
31};