Problem

Given a string s, find the minimum number of characters that must be appended at the end to make s a palindrome.

Examples

Example 1

1
2
3

Input: s = "abede"
Output: 2
Explanation: Appending "ba" at the end gives "abedeba", which is a palindrome.

Example 2

1
2
3

Input: s = "aabb"
Output: 2
Explanation: Appending "aa" at the end gives "aabbaa", which is a palindrome.
Similar Problems

Solution

Method 1 – Greedy Removal and Check

Intuition

To make the string a palindrome by only appending at the end, we want to find the longest palindromic prefix. The minimum number of appends needed is the number of characters at the start that are not part of this palindrome. We can check for the largest suffix of s that is a palindrome, and the answer is the number of characters before this suffix.

Approach

  1. For each position i from 0 to n-1:
  • Check if the substring s[i:] is a palindrome.
  • If it is, the answer is i (the number of characters before this suffix).
  1. Return the minimum i found.
  2. Edge case: If the string is already a palindrome, return 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
  bool isPalindrome(const string& s, int l, int r) {
    while (l < r) {
      if (s[l] != s[r]) return false;
      ++l; --r;
    }
    return true;
  }
  int minAppends(string s) {
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      if (isPalindrome(s, i, n-1)) return i;
    }
    return n-1;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
  boolean isPalindrome(String s, int l, int r) {
    while (l < r) {
      if (s.charAt(l) != s.charAt(r)) return false;
      l++; r--;
    }
    return true;
  }
  public int minAppends(String s) {
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      if (isPalindrome(s, i, n-1)) return i;
    }
    return n-1;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
  def min_appends(self, s: str) -> int:
    def is_palindrome(l: int, r: int) -> bool:
      while l < r:
        if s[l] != s[r]:
          return False
        l += 1
        r -= 1
      return True
    n = len(s)
    for i in range(n):
      if is_palindrome(i, n-1):
        return i
    return n-1

Complexity

  • ⏰ Time complexity: O(n^2), since for each position we may check up to n characters for palindrome.
  • 🧺 Space complexity: O(1), only constant extra space is used.