Minimum Deletions Before Rearranging into a Palindrome
Updated
Problem statement
Given a string S, remove as few characters as possible so that the remaining characters can be rearranged into a palindrome.
The remaining characters may be put in any order. Return the minimum number of deletions. An empty string is a palindrome.
Function
solution(S: String) → intExamples
Example 1
S = "aabbc"return = 0No deletion is needed: rearrange the characters into abcba.
Example 2
S = "abc"return = 2Each letter has an odd count. Keep any one letter and delete the other two.
Example 3
S = "aaabbb"return = 1Delete one a, then rearrange aabbb into abbba.
Example 4
S = ""return = 0The empty string already satisfies the condition.
Constraints
0 <= S.length <= 200000.Scontains only lowercase English letters.
More Marshall Wace interview questions
- Maximum Sum with at Most Three Two-Element TilesPHONE SCREEN · Seen Sep 2025
- Minimum Full Glasses for an Exact Water VolumePHONE SCREEN · Seen Sep 2025
- Smallest Absolute Difference Between Two Array ElementsPHONE SCREEN · Seen Sep 2025
- Maximum Frog Separation with One Upward Jump (Practice Reconstruction)PHONE SCREEN · Seen Jul 2023
- Smallest Larger Integer with Twice the Digit SumPHONE SCREEN · Seen Jul 2023
- Count Squares of Any OrientationPHONE SCREEN · Seen Oct 2019
- Count Letters with Ordered Lowercase and Uppercase OccurrencesOA · Seen Oct 2025
- Maximum Trailing Zeros on a Path with at Most One TurnOA · Seen Oct 2025
- Shortest Subarray Covering an Integer RangeOA · Seen Oct 2025
- Maximum Events in a 60-Second WindowOA · Seen Aug 2025
Similar questions at other companies
- Detect a Straight FlushTemu · PHONE SCREENTemu interview questions
- First Letter to Appear TwiceCisco · PHONE SCREENCisco interview questions
- Halfway Course in a Single TrackCrunchyroll · PHONE SCREENCrunchyroll interview questions
- Portfolio Valuation, Part 1Stripe · PHONE SCREENStripe interview questions
- Single-Condition Product FilterCrowdstrike · PHONE SCREENCrowdstrike interview questions
- Summarize Server Healthcheck LogsNVIDIA · PHONE SCREENNVIDIA interview questions
- Known Words Matching Phone DigitsLinkedIn · PHONE SCREENLinkedIn interview questions
- First Non-Repeated CharacterDell Technologies · PHONE SCREENDell Technologies interview questions
- Convert an Entry List to a MapEPAM · PHONE SCREENEPAM interview questions
- First Non-Repeating CharacterGoldman Sachs · PHONE SCREEN · ONSITE INTERVIEWGoldman Sachs interview questions