## Problem Given a string `s`, find the minimum number of characters to insert (at any positions) to make `s` a palindrome. Also return the count of distinct palindromes that can be formed with exactly that many insertions. ```python def min_insertions_palindrome(s: str) -> tuple[int, int]: """Returns (min_insertions, count_of_distinct_palindromes).""" ... ``` ``` Input: s = "ab" Min insertions: 1 (insert 'a' at end -> "aba", or insert 'b' at start -> "bab") Distinct palindromes: 2 Output: (1, 2) Input: s = "aab" Min insertions: 1 ("aaba" then? No... insert 'a' at end -> "aaba" not palindrome) Correct: insert 'b' before first 'a' -> "baab" YES, or insert 'a' -> "aabaa" YES Output: (1, 2) ``` ## Follow-ups 1. The minimum insertions equal `n - LPS(s)` where LPS is the Longest Palindromic Subsequence length. Prove this. 2. How do you count distinct palindromes? Walk through your approach, handling duplicate characters carefully. 3. What is the time and space complexity of the LPS DP? Can you optimize space from O(n^2) to O(n)? 4. Extend: what is the minimum number of deletions (not insertions) to make `s` a palindrome?

InterviewDB Question

Ways to Make Palindrome: Count Minimum Insertions to Make a String a Palindrome

Question Details

Problem Given a string s, find the minimum number of characters to insert (at any positions) to make s a palindrome. Also return the count of distinct palindromes that can be formed with exactly that many insertions. Follow-ups The minimum insertions equal n - LPS(s) where LPS is the Longest Palindromic Subsequence length. Prove this. How do you count distinct palindromes? Walk through your approach, handling duplicate characters carefully. What is the time and space complexity of the LPS DP? Ca…

Full Details

🔒

Unlock all Hudson River Trading questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a reported interview question from a hudson river trading interview during the oa round.

It covers the following topics: Dynamic Programming, Coding, Oa, Strings .

Topics

Dynamic Programming Coding Oa Strings

Ways to Make Palindrome: Count Minimum Insertions to Make a String a Palindrome

Question Details

Full Details

About This Question

Topics

More Hudson River Trading Interview Questions