README_EN.md

1177. Can Make Palindrome from Substring

中文文档

Description

You are given a string s and array queries where queries[i] = [lefti, righti, ki]. We may rearrange the substring s[lefti...righti] for each query and then choose up to ki of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return a boolean array answer where answer[i] is the result of the ith query queries[i].

Note that each letter is counted individually for replacement, so if, for example s[lefti...righti] = "aaa", and ki = 2, we can only replace two of the letters. Also, note that no query modifies the initial string s.

 

Example :

Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0]: substring = "d", is palidrome.
queries[1]: substring = "bc", is not palidrome.
queries[2]: substring = "abcd", is not palidrome after replacing only 1 character.
queries[3]: substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab".
queries[4]: substring = "abcda", could be changed to "abcba" which is palidrome.

Example 2:

Input: s = "lyb", queries = [[0,1,0],[2,2,1]]
Output: [false,true]

 

Constraints:

• 1 <= s.length, queries.length <= 105
• 0 <= lefti <= righti < s.length
• 0 <= ki <= s.length
• s consists of lowercase English letters.

Solutions

Python3

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        n = len(s)
        cnt = [[0] * 26]
        for i, c in enumerate(s, 1):
            j = ord(c) - ord('a')
            t = cnt[-1][:]
            t[j] += 1
            cnt.append(t)
        ans = []
        for left, right, k in queries:
            x = sum((b - a) & 1 for a, b in zip(cnt[right + 1], cnt[left]))
            ans.append(x // 2 <= k)
        return ans

Java

class Solution {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int n = s.length();
        int[][] cnt = new int[n + 1][26];
        for (int i = 1; i <= n; ++i) {
            int j = s.charAt(i - 1) - 'a';
            for (int k = 0; k < 26; ++k) {
                cnt[i][k] = cnt[i - 1][k];
            }
            cnt[i][j]++;
        }
        List<Boolean> ans = new ArrayList<>();
        for (var q : queries) {
            int left = q[0], right = q[1], k = q[2];
            int x = 0;
            for (int j = 0; j < 26; ++j) {
                x += (cnt[right + 1][j] - cnt[left][j]) & 1;
            }
            ans.add(x / 2 <= k);
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
        int n = s.size();
        int cnt[n + 1][26];
        memset(cnt, 0, sizeof cnt);
        for (int i = 1; i <= n; ++i) {
            int j = s[i - 1] - 'a';
            for (int k = 0; k < 26; ++k) {
                cnt[i][k] = cnt[i - 1][k];
            }
            cnt[i][j]++;
        }
        vector<bool> ans;
        for (auto& q : queries) {
            int left = q[0], right = q[1], k = q[2];
            int x = 0;
            for (int j = 0; j < 26; ++j) {
                x += (cnt[right + 1][j] - cnt[left][j]) & 1;
            }
            ans.emplace_back(x / 2 <= k);
        }
        return ans;
    }
};

Go

func canMakePaliQueries(s string, queries [][]int) (ans []bool) {
	n := len(s)
	cnt := make([][26]int, n+1)
	for i := 1; i <= n; i++ {
		j := s[i-1] - 'a'
		for k := 0; k < 26; k++ {
			cnt[i][k] = cnt[i-1][k]
		}
		cnt[i][j]++
	}
	for _, q := range queries {
		left, right, k := q[0], q[1], q[2]
		x := 0
		for j := 0; j < 26; j++ {
			x += (cnt[right+1][j] - cnt[left][j]) & 1
		}
		ans = append(ans, x/2 <= k)
	}
	return
}

...