amazon logo
Amazon· sde - 1

Amazon OA SDE - 1 , Find number of valid substrings...

Result
Ongoing
Posted
19 Sept 2025
425 reads

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)

  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 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 in t.
    • Similarly, for each 'b' in s, there must be an 'a' as a pair in t.
    • And for each 'c' in s, there must be a 'd' as a pair in t, 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.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Amazon recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!