Welcome To Sora Park

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)P A H N A P L S I I G Y I R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I

Example 3:

Input: s = "A", numRows = 1 Output: "A"

Constraints:

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' and '.'.
• 1 <= numRows <= 1000

class Solution {
public:
    string convert(string s, int numRows) {
        string ans = "";
        int step = (numRows + (numRows - 2));
        int loops = step < 1 ? 1 : (int)ceil((double)s.length() / (double)step);
        int cur = 0, start, end;
        while (ans.length() < s.length())
        {
            for (int i = 0; i < loops; i++)
            {
                start = (step * i) + cur;
                if (cur == 0)
                {
                    if (start < s.length()) ans += s[start];
                }
                else
                {
                    end = (step + (step * i)) - cur;
                    if (start < s.length()) ans += s[start];
                    if (end < s.length() && end > start) ans += s[end];
                }
            }
            cur++;
        }
        return ans;
    }
};

There is an unordered array, P, consisting of integers that are less than 100,000.

Check whether there is a pair of values that can sum up to the given sum, k.

bool test(const vector<int>& arr, int k)
{
	unordered_set<int> unord;
	for (int value : arr)
	{
		if (unord.find(value) != unord.end())
		{
			return true;
		}
		unord.insert(k - value);
	}
	return false;
}

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd" Output: "bb"

Example 3:

Input: s = "a" Output: "a"

Example 4:

Input: s = "ac" Output: "a"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

class Solution {
public:
    string longestPalindrome(string s) {
        string palindrome = "";
        int n = s.length();
        if (n < 2)
        {
            return s;
        }
        
        n = (n * 2) + 1;
        int pals[n];
        memset(pals, 0, sizeof(int) * n);
        pals[0] = 0, pals[1] = 1;
        int centreIndex = 1, rightIndex = 2;
        int maxPalLen = 0, maxCentreIndex = 0;
        int left, diff, start, end;
        
        for (int right = 2; right < n; right++)
        {
            left = (2 * centreIndex) - right;
            diff = (rightIndex - right);
            
            if (diff > 0)
            {
                pals[right] = min(pals[left], diff);
            }
            
            while (((right + pals[right]) < n &&
                    (right - pals[right]) > 0) &&
                   (((right + pals[right] + 1) % 2 == 0) ||
                    (s[(right + pals[right] + 1) / 2] ==
                     s[(right - pals[right] - 1) / 2])))
            {
                pals[right]++;
            }
            
            if (pals[right] > maxPalLen)
            {
                maxPalLen = pals[right];
                maxCentreIndex = right;
            }
            if (right + pals[right] > rightIndex)
            {
                centreIndex = right;
                rightIndex = (right + pals[right]);
            }
        }
        
        start = (maxCentreIndex - maxPalLen) / 2;
        end = start + maxPalLen - 1;
        
        for (int i = start; i <= end; i++)
        {
            palindrome += s[i];
        }
        
        return palindrome;
    }
};

The Manacher's algorithm is the problem of finding the longest substring which is a palindrome.

The time complexity of the algorithm is O(n).

The basic idea of the algorithm is to find the symmetric string on both sides of the centre. For example, abcdcba and madamisimadam. If the length of the string is even, a special character should be added as follows:

• S: abba
• S´: |a|b|b|a|

The length of the right string is 9, 2 * length(S) + 1, which is odd.

Let P be an array of S´:

Each position of the array can be the centre to calculate the length of the palindromic string of the positions.

Depending on the position of the centre, the palindromic lengths are stored as below:

In the array, the centre of the longest palindromic string is at index 4.

Pseudocode

Longest_Palindrome(string S) {
        string S' = S with a bogus character (eg. '|') inserted between each character (including outer boundaries)
        array PalindromeRadii = [0,...,0]
        // The radius of the longest palindrome centered on each place in S'
        // note: length(S') = length(PalindromeRadii) = 2 × length(S) + 1
        
        Center = 0
        Radius = 0
        
        while Center < length(S') 
        {
            // At the start of the loop, Radius is already set to a lower-bound for the longest radius.
            // In the first iteration, Radius is 0, but it can be higher.
            
            // Determine the longest palindrome starting at Center-Radius and going to Center+Radius
            while Center-(Radius+1) >= 0 and Center+(Radius+1) < length(S') and S'[Center-(Radius+1)] = S'[Center+(Radius+1)] {
                Radius = Radius+1
            }             
         
            // Save the radius of the longest palindrome in the array
            PalindromeRadii[Center] = Radius
            
            // Below, Center is incremented.
            // If any precomputed values can be reused, they are.
            // Also, Radius may be set to a value greater than 0
            
            OldCenter = Center
            OldRadius = Radius
            Center = Center+1
            // Radius' default value will be 0, if we reach the end of the following loop. 
            Radius = 0 
            while Center <= OldCenter + OldRadius {
                // Because Center lies inside the old palindrome and every character inside
                // a palindrome has a "mirrored" character reflected across its center, we
                // can use the data that was precomputed for the Center's mirrored point. 
                MirroredCenter = OldCenter - (Center - OldCenter)
                MaxMirroredRadius = OldCenter + OldRadius - Center
                if PalindromeRadii[MirroredCenter] < MaxMirroredRadius {
                    PalindromeRadii[Center] = PalindromeRadii[MirroredCenter]
                    Center = Center+1
                }   
                else if PalindromeRadii[MirroredCenter] > MaxMirroredRadius {
                    PalindromeRadii[Center] = MaxMirroredRadius
                    Center = Center+1
                }   
                else { // PalindromeRadii[MirroredCenter] = MaxMirroredRadius
                    Radius = MaxMirroredRadius
                    break  // exit while loop early
                }   
            }      
        }
        
        longest_palindrome_in_S' = 2*max(PalindromeRadii)+1
        longest_palindrome_in_S = (longest_palindrome_in_S'-1)/2
        return longest_palindrome_in_S 
    }

Code

int longest_palindrome(string s)
{
	string s2 = "";
	for (int i = 0; i < s.length(); i++)
	{
		s2 += '|';
		s2 += s[i];
	}
	s2 += '|';

	int centre = 0, radius = 0;
	int oldCentre, oldRadius;
	int mirrorCentre, maxMirroredRadius;

	vector<int> palindromeNum;
	palindromeNum.resize(s2.length());

	while (centre < s2.length())
	{
		while ((centre - (radius + 1) >= 0) && (centre + (radius + 1) < s2.length()) &&
			s2[centre - (radius + 1)] == s2[centre + (radius + 1)])
		{
			radius++;
		}

		palindromeNum[centre] = radius;
		oldCentre = centre;
		oldRadius = radius;
		centre++;
		radius = 0;

		while (centre <= (oldCentre + oldRadius))
		{
			mirrorCentre = oldCentre - (centre - oldCentre);
			maxMirroredRadius = oldCentre + oldRadius - centre;
			if (palindromeNum[mirrorCentre] < maxMirroredRadius)
			{
				palindromeNum[centre] = palindromeNum[mirrorCentre];
				centre++;
			}
			else if (palindromeNum[mirrorCentre] > maxMirroredRadius)
			{
				palindromeNum[centre] = maxMirroredRadius;
				centre++;
			}
			else
			{
				radius = maxMirroredRadius;
				break;
			}
		}
	}
	return palindromeNum[max_element(palindromeNum.begin(), palindromeNum.end()) - palindromeNum.begin()];
}