Round 1
Questions: To find the length of longest self-sufficient proper substring. A self-sufficient proper substring is one where:
- The substring is not the entire string s.
- 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:
- s is of lowercase letters.
- 1 <= n <= 10^5
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:
- Initialize two pointers,
startandend, both set to the beginning of the string. - Use a frequency map to count occurrences of characters in the current window.
- Expand the
endpointer to include new characters until we encounter a character that is also present outside the current substring. - If a character is found that violates the self-sufficient condition, move the
startpointer to shrink the window until the condition is satisfied again. - Keep track of the maximum length of valid substrings found during this process.
- 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.