Amazon OA SDE - 1 , Find number of valid substrings...
- Result
- Ongoing
- Posted
- 19 Sept 2025
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.
How it went
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.
Questions asked (1)
- 01
Find Valid Substrings with Equal Frequencies
Data Structures & Algorithms · Medium
We are given a string
s, which consists of only 'a's, 'b's, 'c's and 'd's. A stringsis considered valid if for any permutationtofs, 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. - For each 'a' in