Frontend School

Perfect Palindrome Sequence

DSA
hard

Perfect Palindrome Sequence

Hard
String

Overview

At Atlassian, ensuring data integrity and consistency in user-generated content is paramount. One common challenge involves normalizing strings to fit specific structural patterns. This problem asks you to transform a given string into a 'perfect palindrome sequence' with the minimum number of changes, utilizing a special replacement character.

What you need to do / Task

Implement the function minChangesToPerfectPalindrome that takes a string s, an integer targetPalindromeLength L, and a character replacementChar. Your goal is to determine the minimum number of character changes required to transform s into a 'perfect palindrome sequence' of length L.

A string T is defined as a 'perfect palindrome sequence' of length L if every substring of T of length L is a palindrome.

When making changes:

  • If you need to change s[i] to target_char:
    • If s[i] == target_char, no change (cost 0).
    • If s[i] != target_char AND target_char == replacementChar, change s[i] to replacementChar (cost 1).
    • If s[i] != target_char AND target_char != replacementChar, it's impossible to achieve target_char at this position (unless s[i] was already target_char). In this scenario, this particular target pattern is invalid.

Input & output

Function Signature:

function minChangesToPerfectPalindrome(s: string, targetPalindromeLength: number, replacementChar: string): number;
  • s: The input string, consisting of lowercase English letters.
  • targetPalindromeLength: An integer L representing the required length for all palindromic substrings.
  • replacementChar: A single lowercase English letter that can be used to replace any character in s at a cost of 1.
  • Returns: An integer representing the minimum number of changes. If it's impossible to form any valid perfect palindrome sequence under the given constraints, return s.length + 1 (or any value greater than s.length).

Clarifications

  • For L = 1, any string is considered a perfect palindrome sequence (since every single character is a palindrome). In this specific case, 0 changes are needed.
  • The problem involves finding the minimum changes. You should explore all valid target patterns and choose the one with the lowest change count.
  • The length of s can be up to 10^5.

Examples

1

Example 1

Input:

s = "abacaba", targetPalindromeLength = 3, replacementChar = 'x'

Output:

3

Note:

For L=3 (odd), the perfect palindrome sequence must be of the form X Y X Y X Y X... If we choose X='a' and Y='x', the target string is "axaxaxa". Original: "abacaba" Target: "axaxaxa" Differences: ^ ^ ^ Changes needed: s[1] (b->x), s[3] (c->x), s[5] (b->x). Total 3 changes. This is the minimum possible.

2

Example 2

Input:

s = "aaaaa", targetPalindromeLength = 2, replacementChar = 'b'

Output:

0

Note:

For L=2 (even), the perfect palindrome sequence must be of the form X X X X X... If we choose X='a', the target string is "aaaaa". Original: "aaaaa" Target: "aaaaa" Differences: (none) Changes needed: 0. This is the minimum. Note that 'a' is not 'b', but since all original characters are 'a', no changes are needed.

3

Example 3

Input:

s = "abcde", targetPalindromeLength = 4, replacementChar = 'a'

Output:

4

Note:

For L=4 (even), the perfect palindrome sequence must be of the form X X X X X... If we choose X='a', the target string is "aaaaa". Original: "abcde" Target: "aaaaa" Differences: ^ ^ ^ ^ Changes needed: s[1] (b->a), s[2] (c->a), s[3] (d->a), s[4] (e->a). Total 4 changes. This is the minimum.

Constraints

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • 1 <= targetPalindromeLength <= s.length
  • s consists only of lowercase English letters ('a'-'z')
  • replacementChar is a single lowercase English letter ('a'-'z')

What interviewers evaluate

  • Algorithmic Correctness: Correctly identifying the structural properties of a 'perfect palindrome sequence' for varying L values.
  • Edge Case Handling: Correctly handling L=1 and scenarios where a target pattern is impossible due to replacementChar constraints.
  • Efficiency: Developing an algorithm that runs within the time limits (O(alphabet_size^2 * N) where alphabet_size is small).
  • Code Clarity & Structure: Writing clean, well-organized, and readable code with appropriate helper functions.

Loading editor...