Distinct Palindrome Partitions
Updated
Problem statement
Return every way to split the entire string s into nonempty, contiguous pieces such that each piece is a palindrome and no two pieces in the same partition have the same string value. Pieces must cover the string in their original order without gaps or overlap.
For this exercise, p=0 selects the base problem with unrestricted piece lengths. When p>0, every piece must have exactly p characters. This is a length per piece, not a required number of pieces.
Return a string matrix, with one partition per row. Piece values must be distinct within a row; a value may appear in different rows. Return rows in lexicographic order: compare the first differing strings by ordinary lowercase letter order, with a proper prefix preceding the longer string. Return an empty matrix if there is no valid partition. Do not return only a count, and do not modify the input string.
Function
distinctPalindromePartitions(s: String, p: int) → String[][]Examples
Example 1
s = "aab"p = 0return = [["aa","b"]]The usual split ["a","a","b"] is invalid because "a" appears twice in the same row. The only valid full partition is ["aa","b"].
Example 2
s = "aabb"p = 2return = [["aa","bb"]]With p=2, the sole possible cut pattern is ["aa","bb"]. Both pieces are palindromes, and their values are distinct.
Constraints
- For this exercise, assume 1 <= s.length <= 12.
- s contains only lowercase ASCII letters a through z.
- For this exercise, assume 0 <= p <= 12.
More Morgan Stanley Onsite Interview questions
- Generate Strings of Length at Least ThreeONSITE INTERVIEW · Seen Sep 2026
- Maximum Concurrent ProcessesOA · ONSITE INTERVIEW · Seen Sep 2026
- Kth Largest Array ElementONSITE INTERVIEW · Seen Jul 2026
- Run-Length Encode Consecutive Letter RunsONSITE INTERVIEW · Seen Jul 2026
- Maximum Edge Removals for Two TravelersONSITE INTERVIEW · Seen Oct 2025
- Remove K DigitsONSITE INTERVIEW · Seen Oct 2025
- Count Ideal ArraysONSITE INTERVIEW · Seen Aug 2023
- LFU Cache OperationsONSITE INTERVIEW · Seen Aug 2023
- All-Pairs Shortest PathsOA · ONSITE INTERVIEW · Seen Feb 2022
- Fibonacci with Input ValidationONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Count Complete Tic-Tac-Toe GamesDecagon · PHONE SCREEN · ONSITE INTERVIEWDecagon interview questions
- Enumerate Right-and-Down Matrix PathsOracle · ONSITE INTERVIEWOracle interview questions
- Beautiful ArrangementMathWorks · ONSITE INTERVIEWMathWorks interview questions
- First Valid Word SegmentationAmazon · ONSITE INTERVIEW
- Generate One-Two Strings with Sum NGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Unique Unordered Dice OutcomesMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Find a Subset of Exactly K Elements with a Target SumJP Morgan Chase · ONSITE INTERVIEWJP Morgan Chase interview questions
- Count and Score Distinct Hat AssignmentsRoblox · ONSITE INTERVIEWRoblox interview questions
- Partition a Card Deck into FifteensMeta · ONSITE INTERVIEWMeta interview questions
- Maximum Currency Conversion Along a Simple PathRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
Interview reports that mention this question
Morgan Stanley interview experiences
- Morgan Stanley New Grad Technology Analyst: 2 Experiences
- Morgan Stanley Intern Oldest Loops: 5 Experiences (Part 5 of 5)
- Morgan Stanley Intern OOP Loops: 5 Experiences (Part 4 of 5)
- Morgan Stanley Intern Earlier Loops: 5 Experiences (Part 3 of 5)
- Morgan Stanley Intern Tech Rounds: 5 Experiences (Part 2 of 5)