Meta·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Meta SWE coding round with a substring problem that looks trivial until you actually read the edge cases carefully. Came away feeling okay about it but not totally confident.

Questions Asked (1)

Given a lowercase string, find the shortest substring where all characters are distinct. If there are ties on length, return the leftmost one. The answer length is capped at 3, so you only need to check lengths 1, 2, and 3.

Algorithms & Data Structures

Author's notes

My first instinct was to reach for a sliding window and I started coding that up before realizing the cap at length 3 makes this way simpler.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Since the answer length is capped at 3, check for valid substrings of length 1, then 2, then 3, returning the first one found. For each length, scan the string from left to right and return the leftmost substring with all distinct characters. If none found, return an empty string.

Pro tip: Clarify with the interviewer whether the answer should be the substring itself or its length, and confirm the behavior when no valid substring exists (e.g., return empty string). This shows attention to detail and avoids wasted effort.

1. Clarify requirements and edge cases

Confirm the return type (substring or length), the cap of 3, and what to return if no valid substring exists. Also consider empty string input.

2. Check length 1

Any single character is trivially distinct. Return the first character if the string is non-empty.

3. Check length 2

Scan the string from left to right; for each adjacent pair, check if the two characters are different. Return the first such pair.

4. Check length 3

Scan the string from left to right; for each triplet, check if all three characters are distinct. Return the first such triplet.

5. Handle no valid substring

If no valid substring of length 1, 2, or 3 is found, return an empty string (or as clarified).

Key Points to Mention

Time complexity: O(n) since we only check lengths 1, 2, and 3, each requiring a single pass.
Space complexity: O(1) as we only use a few variables for comparisons.
Early termination: return as soon as a valid substring is found, ensuring leftmost tie-breaking.
Edge cases: empty string, string length less than 3, and strings with no valid substring (e.g., all same characters).
The cap of 3 simplifies the problem; without it, a sliding window approach would be needed.
Correctness: checking lengths in increasing order guarantees the shortest substring, and left-to-right scanning guarantees the leftmost.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.