We are given a string s, we make queries on it.
For each query queries[i] = [left,right,x], the substring from s[left] to s[right]
can be rearranged, then we choose up to x of them to replace with any lowercase English letter.
If the substring is possible to be a palindrome string after performing the above operations, the result of the query is true, else false.
Return an array result[] where result[i] is the result of i-th query.
The initial string is never modified by any query.
Constraints:
1<=s.length, queries.size <= 10^5
0<=queries[i][0] <= queries[i][1] <s.length
0<=queries[i][2] <= s.length
s only contains lowercase English alphabets.
Solution:
If x greater than or equal to half the length of the substring in the query than we can form a palindrome, and can return true, else
For each query, we need to find how many character occurs an odd number of times, since only such letter needs to be changed.
Then we will have 2 cases:
Case 1: length of substring is odd
if x>=(odd-1)/2 then true
Case 2: length of substring is even
if x>=odd/2 then true
Now to calculate the frequency of all letters for each substring we can not iterate the substring for each query since it will give time limit exceed error. So we make a matrix of row size of the length of string s and column size 26. matrix[i] stores occurrence of each alphabet till s[i].
Code:
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
vector<bool> result;
int n,odd=0,x;
vector<vector<int>> mat(s.length(),vector<int>(26,0));
for(int i=0;i<s.length();i++)
{
if(i!=0)
mat[i]=mat[i-1];
mat[i][s[i]-'a']++;
}
for(int i=0;i<queries.size();i++)
{
n=queries[i][1]-queries[i][0]+1;
if(queries[i][2]>=(n/2))
{
result.push_back(true);
continue;
}
odd=0;
for(int j=0;j<26;j++)
{
x=mat[queries[i][1]][j];
if(queries[i][0]!=0)
x-=mat[queries[i][0]-1][j];
if(x%2!=0)
odd++;
}
if(n%2==0&&queries[i][2]>=(odd/2))
{
result.push_back(true);
continue;
}
if(n%2!=0&&queries[i][2]>=((odd-1)/2))
{
result.push_back(true);
continue;
}
result.push_back(false);
}
return result;
}
Do share the post if you find it helpful and comment if you have some new insights about the problem.
Happy Programming
Programming ninja
If you have any doubts or any new insights, please share ConversionConversion EmoticonEmoticon