Today I have done leetcode's September LeetCoding Challenge with cpp.

September LeetCoding Challenge 20

Description

Shortest Palindrome

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of lowercase English letters only.

Solution

class Solution {
  int solve(const string &s) {
    string rs = string(s.rbegin(), s.rend());
    string ns = s + '#' + rs;
    vector<int> c(ns.length());
    int i = 1;
    int k = 0;
    while(i < ns.length()) {
      if(ns[i] == ns[k]) {
        k += 1;
        c[i] = k;
        i += 1;
      } else {
        if(k > 0) {
          k = c[k - 1];
        } else {
          c[i] = 0;
          i += 1;
        }
      }
    }
    return c.back();
  }
public:
  string shortestPalindrome(string s) {
    int count = solve(s);
    return string(s.rbegin(), s.rend()).substr(0, s.length() - count) + s;
  }
};