Common Prefix Length
Updated
Problem statement
You are given an array of strings inputs. Answer the same question for each string.
For a string s, look at each of its suffixes: the part of s that starts at index 0 (all of s), the part that starts at index 1, and so on, down to the last character alone. For each suffix, find the length of the longest common prefix of that suffix and s, that is, how many characters they share from the start before the first difference. Add up these lengths.
Return an array whose element i is the sum for inputs[i].
Function
commonPrefix(inputs: String[]) → long[]Examples
Example 1
inputs = ["abcabcd"]return = [10]The suffixes of "abcabcd" are "abcabcd", "bcabcd", "cabcd", "abcd", "bcd", "cd" and "d". Their common prefixes with "abcabcd" have lengths 7, 0, 0, 3, 0, 0 and 0. The sum is 7 + 0 + 0 + 3 + 0 + 0 + 0 = 10.
Example 2
inputs = ["ababaa"]return = [11]The suffixes are "ababaa", "babaa", "abaa", "baa", "aa" and "a". Their common prefixes with "ababaa" have lengths 6, 0, 3, 0, 1 and 1, which add up to 11.
Example 3
inputs = ["aa"]return = [3]The suffixes are "aa" and "a". Their common prefixes with "aa" have lengths 2 and 1, so the sum is 3.
Example 4
inputs = ["abab", "z"]return = [6, 1]Each string gets its own sum. For "abab", the suffixes "abab", "bab", "ab" and "b" give lengths 4, 0, 2 and 0, so the sum is 6. For "z", the only suffix is "z" itself, so the sum is 1.
Constraints
1 <= inputs.length <= 101 <= inputs[i].length <= 105inputs[i]consists of only lowercase English letters.
More Airbnb Online Assessment questions
- Task Management SystemOA · Seen Nov 2026
- Recipe Management SystemOA · Seen Nov 2026
- Progressive Banking SystemOA · Seen Nov 2026
- Credit Accounts with Scheduled TransfersOA · Seen Oct 2026
- Parcel Attribute Store with TTLOA · Seen Oct 2026
- Parcel Event TrackingOA · Seen Oct 2026
- Median Home Price by CityOA · Seen Sep 2026
- In-Memory File SystemOA · Seen Sep 2026
- Worker Management (Promotion Track), Part 4: Full-Shift Double PayOA · Seen Sep 2026
- Worker Management (Promotion Track), Part 3: Promotions and SalaryOA · Seen Sep 2026
Similar questions at other companies
- Lexicographically Smallest Grid Path with One Letter ChangeInfosys · OAInfosys interview questions
- Minimum Merge ConflictsAmazon · OA
- Incident MonitorStripe · OAStripe interview questions
- Balance a Chemical EquationMicrosoft · OAMicrosoft interview questions
- Longest Repeated Letter Block with Adjacent SwapsIntuit · OAIntuit interview questions
- Count Substrings Matching with One Adjacent SwapInMobi · OAInMobi interview questions
- Binary CircuitAkuna Capital · OAAkuna Capital interview questions
- String Formation (Also for AI/ML Software Engineer Intern :)Snowflake · OASnowflake interview questions
- Binary Sorting Rounds After FlipsVisa · OAVisa interview questions
- Minimum Numeric Code TransformationAdobe · OAAdobe interview questions
Interview reports that mention this question
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, Diplomacy Game: 19 Experiences (Part 4 of 7)