Category: geeksforgeeks

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⁶

Solution:

To determine the minimum characters to be added at the front of a string to make it a palindrome, we can solve the problem efficiently using a technique involving the longest prefix of the string that is also a suffix (LPS). This can be computed using the KMP algorithm. Below is the explanation, followed by the implementation.

Key Observation:

To make the string a palindrome by adding only characters to the front:

• We need to find the longest suffix of the string (starting at the end) that is already a palindrome.
• Once this suffix is identified, the remaining prefix of the string (which isn’t part of that palindromic suffix) will need to be reversed and added to the front of the string. The count of these characters is the output.

This amounts to finding:

1. The longest prefix-suffix (LPS) of the string concatenated with its reverse (using a special separator character to avoid false matches).

Let’s break this into steps.

Steps to Find the Minimum Characters:

1. Concatenate the String and Its Reverse:
   • Create a new string: temp = s + "$" + reverse(s) (we use $ or any separator to distinguish the reversed part from the original string).
2. Compute Longest Prefix Suffix (LPS):
   • Use the KMP (Knuth-Morris-Pratt) algorithm on temp to compute the LPS array.
   • The LPS array gives us the length of the longest prefix of temp that is also a suffix. This indicates the maximum part of s (from the start) that matches the reverse part.
3. Calculate Minimum Characters to Add:
   • Subtract the longest prefix-suffix from the length of the original string:

Minimum characters to add = s.length() - LPS[length of temp - 1]

Implementation in C++:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// Function to compute the LPS array (used in KMP algorithm)
vector<int> computeLPS(const string& str) {
    int n = str.length();
    vector<int> lps(n, 0); // LPS array
    int len = 0;          // Length of previous longest prefix suffix
    int i = 1;

    // Compute LPS array
    while (i < n) {
        if (str[i] == str[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1]; // Backtrack
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// Function to find minimum characters to add at front to make the string palindrome
int minCharsToMakePalindrome(const string& s) {
    string reversedStr = s;
    reverse(reversedStr.begin(), reversedStr.end());

    // Create the concatenated string
    string temp = s + "$" + reversedStr;

    // Compute LPS array for the concatenated string
    vector<int> lps = computeLPS(temp);

    // Length of the longest palindromic suffix
    int longestPalindromicPrefix = lps.back();

    // Minimum characters to add = length of s - longest palindromic prefix
    return s.length() - longestPalindromicPrefix;
}

int main() {
    string s;
    cout << "Enter string: ";
    cin >> s;

    int result = minCharsToMakePalindrome(s);

    cout << "Minimum characters to add: " << result << endl;

    return 0;
}

Explanation of Code:

1. Reverse the String:
   • Create a reversed copy of s (reversedStr).
2. Concatenate s, $, and reversedStr:
   • This ensures we identify the longest part of s that matches the reversed portion.
   Example:
   If s = “aacecaaa”, then temp = “aacecaaa$aaacecaa”.
3. Compute LPS Array:
   • Use the KMP algorithm to compute the longest prefix that is also a suffix for temp.
4. Find the Num of Characters to Add:
   • Subtract the length of the longest palindromic prefix from the total length of s.

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

Key Observations:

1. A rotated sorted array is a sorted array that has been rotated at some pivot point. For example:
   • Original array: [1, 2, 3, 4, 5]
   • Rotated arrays: [4, 5, 1, 2, 3], [3, 4, 5, 1, 2]
2. Minimum Element:
   • The minimum element is the only element in the rotated array that is smaller than its predecessor.
   • Alternatively, in the case of no rotation (e.g., [1, 2, 3, 4, 5]), the first element is the smallest.
3. Binary Search Approach:
   • Since the array is sorted and rotated, we can use binary search to identify the minimum element in O(log n) time.

Steps to Solve:

1. Binary Search:
   • Set two pointers: low = 0 (start of array) and high = n-1 (end of array).
   • While low < high, compute the middle index: mid = low + (high - low) / 2.
   • Depending on the relationship between arr[mid] and arr[high]:
     • If arr[mid] > arr[high]: The minimum must lie in the right half of the array (set low = mid + 1).
     • Otherwise, the minimum must be in the left half or at mid (set high = mid).
   • When low == high, the minimum element is at index low.
2. Return the Result:
   • Output the element at arr[low].

Algorithm Complexity:

• Time Complexity:
  Binary search operates in O(log n) time due to halving the search space in every iteration.
• Space Complexity:
  The algorithm uses O(1) space as we only manipulate indices and access the array directly.

Implementation in C++:

Here is the efficient implementation:

#include <iostream>
#include <vector>
using namespace std;

int findMinimum(const vector<int>& arr) {
    int low = 0, high = arr.size() - 1;

    // Binary search to find the minimum element
    while (low < high) {
        int mid = low + (high - low) / 2;

        // If middle element is greater than the last element,
        // the minimum must be in the right half
        if (arr[mid] > arr[high]) {
            low = mid + 1;
        } 
        // Otherwise, the minimum is in the left half (or could be at mid)
        else {
            high = mid;
        }
    }

    // At this point, low == high and points to the minimum element
    return arr[low];
}

int main() {
    vector<int> arr = {4, 5, 6, 7, 0, 1, 2}; // Example rotated array
    cout << "The minimum element is: " << findMinimum(arr) << endl;

    return 0;
}