Min Chars to Add for Palindrome

Given a string s,the task is to find the minimum characters to be added at the front to make the string palindrome.

Note: A palindrome string is a sequence of characters that reads the same forward and backward.

Examples:

Input: s = "abc"
Output: 2
Explanation: Add 'b' and 'c' at front of above string to make it palindrome : "cbabc"

Input: s = "aacecaaaa"
Output: 2
Explanation: Add 2 a's at front of above string to make it palindrome : "aaaacecaaaa"

Constraints:
1 <= s.size() <= 10⁶

Approach 01:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
    static std::vector<int> computeLPS(const std::string &str) {
        int strLength = str.length();
        int prefixIndex = 0;
        int suffixIndex = 1;
        std::vector<int> lps(strLength, 0);

        while (suffixIndex < strLength) {
            if (str[prefixIndex] == str[suffixIndex]) {
                prefixIndex++;
                lps[suffixIndex] = prefixIndex;
                suffixIndex++;
            } else {
                if (prefixIndex == 0) {
                    lps[suffixIndex] = 0;
                    suffixIndex++;
                } else {
                    prefixIndex = lps[prefixIndex - 1];
                }
            }
        }
        return lps;
    }

    static int minChar(const std::string &str) {
        std::string reverseStr = str;
        std::reverse(reverseStr.begin(), reverseStr.end());
        std::string concatenatedStr = str + "#" + reverseStr;

        std::vector<int> lps = computeLPS(concatenatedStr);
        return str.length() - lps[lps.size() - 1];
    }
};

class Solution:
    @staticmethod
    def computeLPS(string):
        string_length = len(string)
        prefix_index = 0
        suffix_index = 1
        lps = [0] * string_length

        while suffix_index < string_length:
            if string[prefix_index] == string[suffix_index]:
                prefix_index += 1
                lps[suffix_index] = prefix_index
                suffix_index += 1
            else:
                if prefix_index == 0:
                    lps[suffix_index] = 0
                    suffix_index += 1
                else:
                    prefix_index = lps[prefix_index - 1]
        return lps

    @staticmethod
    def minChar(string):
        reverse_string = string[::-1]
        concatenated_string = string + "#" + reverse_string

        lps = Solution.computeLPS(concatenated_string)
        return len(string) - lps[-1]

Time Complexity

• Reversing the string:

  The reverse operation iterates over the input string once. Let the length of the string be \(N\). This takes \(O(N)\).

• Concatenation of strings:

  Creating the concatenated string involves copying the original string, a delimiter, and the reversed string, which takes \(O(N)\).

• Computing the LPS array:

  The computeLPS function processes the concatenated string of length \(2N + 1\). Since LPS computation is linear, this step takes \(O(2N + 1) = O(N)\).

• Overall Time Complexity:

  Adding these steps, the overall time complexity is \(O(N)\).

Space Complexity

• Reversed string:

  A separate string of size \(N\) is created to store the reversed version of the input string. This contributes \(O(N)\).

• Concatenated string:

  A new string of size \(2N + 1\) is created for the concatenation. This contributes \(O(N)\).

• LPS array:

  An LPS array of size \(2N + 1\) is created, which takes \(O(N)\) space.

• Overall Space Complexity:

  The overall space complexity is \(O(N)\), as the memory usage is dominated by the reversed string, concatenated string, and LPS array.