Amazon OA SDE - 1 , Find number of valid substrings...
Summary
I recently took the Amazon Online Assessment for SDE-1. The primary challenge was a string manipulation problem requiring me to identify valid substrings based on character frequency balance.
Full Experience
During my Amazon OA for the SDE-1 role, I was presented with a problem that involved analyzing substrings of a given string. The string comprised only 'a', 'b', 'c', and 'd' characters. The core task was to determine if a substring was 'valid', which was defined by a specific condition: for any permutation of the substring, 'a' must have 'b' as a pair, and similarly, 'c' must have 'd' as a pair. This essentially boils down to checking if the frequency of 'a' equals 'b', and the frequency of 'c' equals 'd' within that substring. I needed to find the total count of such valid substrings. I found the problem statement to be clear and the examples helpful in understanding the conditions.
Interview Questions (1)
We are given a string s, which consists of only 'a's, 'b's, 'c's and 'd's. A string s is considered valid if for any permutation t of s, the following conditions hold:
- For each 'a' in
s, there must be a 'b' as a pair int. - Similarly, for each 'b' in
s, there must be an 'a' as a pair int. - And for each 'c' in
s, there must be a 'd' as a pair int, and vice versa.
Example 1:
s = "abcd"
Output: Valid (because we can achieve a permutation like "badc")
Example 2:
s = "aab"
Output: Not Valid (because for one of the 'a's, there is no 'b' to pair with)
The problem states that for a substring to be valid, it must satisfy: freq[a] == freq[b] && freq[c] == freq[d].
The task is to find all valid substrings of the given string s.