Problem Link
Setter: Hasan Jaddouh
Tester: Amr Mahmoud
Editorialist: Bhuvnesh Jain
Difficulty
MEDIUM
Prerequisites
Combinatorics
Problem
Given a string S and an integer K. Find the number of strings, T, having the same length as S such that T is palindrome and the hamming distance between S and T is at most K.
Some Hints/Tricks
Try to think about how changing an index in left part or sting S, forces us to operate on the corresponding right index to maintain the palindromic property satisfied in final string. Try to find a combinatorial formula for it. Precompute some sums (or formulas) to get an overall complexity of O(n).
Explanation
The question can be reframed as “Find the number of strings which can be formed by changing at most K characters in S, so that resulting string becomes a palindrome.” Assume, 0-based indexing in the editorial.
The strings T that we need to form should be palindrome. This restricts how we modify some characters from string S. Thus, we define 2 terms here:
- Fixed: The set of those indices, $i (< {\frac{n}{2}})$, such that $S[i] == S[n-1-i]$.
- nonFixed: The set of those indices, $i (< {\frac{n}{2}})$, such that $S[i] \neq S[n-1-i]$.
Based on these terms, we can clearly see that the all possible strings, with given counts of “Fixed” and “nonFixed” indices, will give the same answer. This is because the answer depends on whether we chose to perform an operation on given index or not and this may force us to perform some operation on another index so that final string remains palindrome. These operations don’t depend on the characters present at that location in the string.
Thus, to calculate the complete answer, we need to evaluate 2 functions, namely:
- $f1(Fixed, k)$ = returns the number of ways to change "Fixed" indices so that palindrome condition is satisfied at those indices, with the condition that maximum of $k$ changes can be made.
- $f2(nonFixed, k)$ = returns the number of ways to change "nonFixed" indices so that palindrome condition is satisfied at those indices, with the condition that exactly $k$ changes can be made.
From the definition of above 2 functions, it is easy to see that the final answer is as follows:
F(S, k) = \sum\limits_{i = 0}^{i = k} f1(Fixed, k - i) * f2(nonFixed, i)
Some simplification, before we proceed (assuming we can implement the above functions efficiently). What happens when the length of the given string is odd. The middle character will be not be treated as “Fixed” or “nonFixed”. But, it is clear that we can change this character without affecting the palindromic property in final string. To fix this, we can either change that character or not. Thus, final answer, in this case, would be as follows:
ans = F(S, k) + 25 * F(S, k-1).
Now, let us come back to the evaluation of functions f1(Fixed, k) and f2(nonFixed, k) defined before. These are given by following formulas :
f1(Fixed, k) = \sum\limits_{x = 0}^{x = floor(k/2)} {{{Fixed}\choose{x}} {25}^{x}}
f2(nonFixed, x + 2*(nonFixed - x) <= k) = {{{nonFixed}\choose{x}} * {2}^{x} * {24}^{nonFixed-x}}, provided that (x >= 0 \text{ and } x <= nonFixed)
The reasoning is as follows:
- In "fixed" case, the condition of the palindrome is already satisfied. So, if we change a character at fixed index, (say $i$), we need to change it at another location, (namely $(n-i-1)$). Thus, we every time need to make at least 2 changes in $S$. Thus, we select the number of indices we want to make changes in and then make changes in them. The number of ways to chose the indices is ${{Fixed}\choose{x}}$ and the number of ways is ${25}^{x}$ as there are $25$ different possible characters to be replaced at each location.
- In "non_fixed" case, the condition of the palindrome is not satisfied. So, we can either change both the indices, $i$ and $(n-i-1)$, or change only one of them. But change has to be applied to ensure final string has the palindrome condition satisfied. If we change both of them, then both of them must be same and there are remaining $24$ characters to chose from. If we change only one of them, then we have only 2 choices, either change $S[i]$ and make it equal to $S[n-i-1]$ and vice-versa.
Implementing the above full idea naively will take O(N^2) time as there will be double summations. The trick is to pre-compute the function f1(Fixed, k) and compute the final answer, F(S, k) in such a way that function f2(nonFixed, k) is computed on the fly.
To compute f1(Fixed, k) for all values of x, such that 0 <= x <= k, we can make one observation. The value of f1(Fixed, k) will be same as f1(fixed, k-1), if k is odd. Otherwise, the only additional contribution is of last term i.e. {{Fixed}\choose{k/2}} {25}^{k/2}.
To get more idea about the implementation, refer to editorialist solution. In case of any doubt’s, feel free to comment below.
Time Complexity
O(N), per test case. Assuming all precomputations are also done in O(\text{MAX VALUE}).
Space Complexity
O(N)
