Count Repeated Substrings
Updated
Problem statement
Given a string s, count how many different substrings appear in s at least twice.
A substring is a non-empty block of letters that sit next to each other in s. Two copies of a substring may overlap: in "aaa", the substring "aa" starts at positions 0 and 1, so it appears twice. Each different substring is counted once, however many times it appears.
The answer can be larger than 2^31 - 1, so return it as a 64-bit integer.
Function
countRepeatedSubstrings(s: String) → longExamples
Example 1
s = "abcab"return = 3Three different substrings appear at least twice: "a" (positions 0 and 3), "b" (positions 1 and 4) and "ab" (positions 0 and 3). Every other substring appears once, so the answer is 3.
Example 2
s = "aaaa"return = 3"a" appears 4 times, "aa" 3 times and "aaa" twice (starting at positions 0 and 1; these two copies overlap, which is allowed). "aaaa" appears once. Each repeated substring is counted once, so the answer is 3.
Example 3
s = "xyz"return = 0All three letters are different, so every substring appears exactly once. The answer is 0.
Constraints
1 <= s.length <= 150000scontains only lowercase English letters.
More Rippling Onsite Interview questions
- Filter, Sort, and Deduplicate Scheduled TasksPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Stateful Log Transform and SearchPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Camel CardsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Corporate Card Expense RulesOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Limit an Organization Tree's HeightPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Delivery Cost TrackerPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Maximum Currency Conversion Along a Simple PathPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Top K Frequent WordsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Future-Effective Employee SalaryONSITE INTERVIEW · Seen Aug 2026
- Filter and Sort Scheduled TasksONSITE INTERVIEW · Seen Jul 2026
Similar questions at other companies
- Highlight and Rank Overlapping CitationsHarvey · ONSITE INTERVIEWHarvey interview questions
- Process Shopping Records, Promotions, and Display OrderInstacart · PHONE SCREEN · ONSITE INTERVIEWInstacart interview questions
- Autocomplete SystemPinterest · ONSITE INTERVIEWPinterest interview questions
- Number of AtomsAmazon · ONSITE INTERVIEW
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- Keyboard Autocomplete SuggestionsLyft · ONSITE INTERVIEWLyft interview questions
- Query JSON Records with WHERE and ORDER BYGitHub · ONSITE INTERVIEW
- Map and Accumulate Learning QueriesPalantir · ONSITE INTERVIEWPalantir interview questions
- Sort by Odd-Position Digit SumPelatro · ONSITE INTERVIEW
- Transform Dotted Keys into a Nested MapProofpoint · ONSITE INTERVIEW
Interview reports that mention this question
Rippling interview experiences
- Rippling No-Level Onsite Loops: 24 Experiences (Part 5 of 6)
- Rippling No-Level Screens and Loops: 18 Experiences (Part 4 of 6)
- Rippling No-Level Coding Screens: 37 Experiences (Part 3 of 6)
- Rippling No-Level Design, Screens: 30 Experiences (Part 2 of 6)
- Rippling SWE Interviews, No Level: 156 Experiences (Part 1 of 6)