FastPrepShortest Uncommon Substring
Problems/Shortest Uncommon Substring

Shortest Uncommon Substring

Airbnb logoAirbnb● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Airbnb onsite coding round for a senior machine learning engineer role (full-time). The report names the coding question but gives no statement, examples, limits or tie rules.

We used the standard form of this well-known exercise: for each string in an array, find its shortest substring that appears in no other string. We chose the tie rule (the lexicographically smallest substring), the empty-string answer when nothing qualifies, that equal strings at different positions block each other, the limits (2 to 100 strings of 1 to 20 lowercase letters) and the examples.

Our version is about 75% the same as the reported question.

You are given an array arr of n non-empty strings. For each index i, find the shortest substring of arr[i] that does not appear in any other string of arr. Return an array answer of length n where answer[i] is that substring.

If more than one substring of that shortest length qualifies, answer[i] is the lexicographically smallest of them. If no substring of arr[i] qualifies, answer[i] is the empty string "".

A substring is a contiguous, non-empty run of characters in a string. The other strings are arr[j] for every index j != i, so when the same string appears at two indices, each copy blocks the other. A substring may appear more than once inside arr[i] itself.

Function

shortestSubstrings(arr: String[]) → String[]

Examples

Example 1

arr = ["cat","act","tac"]return = ["at","ct","ta"]

Every single letter (a, c, t) appears in all three strings, so no answer has length 1.

For "cat", the length-2 substrings are "ca" and "at". Neither appears in "act" or "tac", so both qualify, and the lexicographically smaller one, "at", is the answer.

For "act", "ac" also appears in "tac", but "ct" appears nowhere else, so the answer is "ct". For "tac", "ac" appears in "act", and "ta" appears nowhere else, so the answer is "ta".

Example 2

arr = ["ab","ab","abc"]return = ["","","c"]

Indices 0 and 1 hold the same string. Each substring of "ab" at index 0 also appears in the string at index 1, so index 0 gets "", and index 1 does too for the same reason.

For "abc", the letter c is not in "ab", so the answer is "c".

Example 3

arr = ["ab","a","b"]return = ["ab","",""]

For "ab", the letter a appears in "a" and the letter b appears in "b". The only substring left is the whole string "ab", which is not in either other string, so it is the answer.

The strings "a" and "b" each have one substring, and it appears in "ab", so both answers are "".

Constraints

  • n == arr.length
  • 2 <= n <= 100
  • 1 <= arr[i].length <= 20
  • arr[i] consists only of lowercase English letters.

More Airbnb interview questions

  • Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Superhost EligibilityONSITE INTERVIEW · Seen Sep 2026
  • Call History ManagerONSITE INTERVIEW · Seen Sep 2022
  • Russian Doll EnvelopesONSITE INTERVIEW · Seen Sep 2022
  • All O(1) Data StructureONSITE INTERVIEW · Seen Jul 2022
  • Cheapest Flight with Its PathOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
  • Alien DictionaryPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2019
  • Task Management SystemOA · Seen Nov 2026
  • Recipe Management SystemOA · Seen Nov 2026
  • Progressive Banking SystemOA · Seen Nov 2026

Similar questions at other companies

  • Longest Consecutive Login StreakAmazon · ONSITE INTERVIEW
  • Group AnagramsMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Word BreakMoveworks · ONSITE INTERVIEWMoveworks interview questions
  • Find Duplicate Element PairsGoogle · ONSITE INTERVIEWGoogle interview questions
  • Detect Cross-Doctor Prescription Pairs Within 30 DaysOracle · ONSITE INTERVIEWOracle interview questions
  • Invalid TransactionsBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Query Log MatchDatadog · PHONE SCREEN · ONSITE INTERVIEWDatadog interview questions
  • Most Frequent Call Path in Interleaved LogsRoblox · ONSITE INTERVIEWRoblox interview questions
  • Group Shifted StringsMathWorks · ONSITE INTERVIEWMathWorks interview questions
  • Deep Merge with a Conflict ResolverAutodesk · ONSITE INTERVIEWAutodesk interview questions

Airbnb interview experiences

  • Airbnb SWE OA: Four-Level Banking System: 1 Experience
  • Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
  • Airbnb Intern Phone Interviews: 21 Experiences (Part 7 of 7)
  • Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
  • Airbnb Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)
  • Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)
All Airbnb interview questionsSee Airbnb hiring insights
Saved
class Solution {
    public String[] shortestSubstrings(String[] arr) {
        // Write your code here.
    }
}
Checking account…