Panda Guru LogoPanda
Guru

Amazon OA

Round 1

Questions: To find the length of longest self-sufficient proper substring. A self-sufficient proper substring is one where:

  1. The substring is not the entire string s.
  2. No letter that occurs inside the substring also occurs outside the substring.

Given the string fullString of length n, find the length of its longest self-sufficient proper substring. If none exists, return 0.

Example:

fullString = "amazonservices" Output = 11 (zonservices)

Input:

Output: The length of the longest self-sufficient string.

Candidate's Approach

To solve this problem, we can use a sliding window approach along with a frequency map to track the characters in the current substring. The steps are as follows:

  1. Initialize two pointers, start and end, both set to the beginning of the string.
  2. Use a frequency map to count occurrences of characters in the current window.
  3. Expand the end pointer to include new characters until we encounter a character that is also present outside the current substring.
  4. If a character is found that violates the self-sufficient condition, move the start pointer to shrink the window until the condition is satisfied again.
  5. Keep track of the maximum length of valid substrings found during this process.
  6. Return the maximum length found, or 0 if no valid substring exists.

Challenges may include efficiently managing the frequency map and ensuring that the window is adjusted correctly.

Interviewer's Feedback

No feedback provided.