Shortest Uncommon Substring
Updated
Problem statement
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.length2 <= n <= 1001 <= arr[i].length <= 20arr[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)