Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1177.html

1177. Can Make Palindrome from Substring

Level

Medium

Description

Given a string s, we make queries on substrings of s.

For each query queries[i] = [left, right, k], we may rearrange the substring s[left], ..., s[right], and then choose up to k 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 an array answer[], where answer[i] is the result of the i-th query queries[i].

Note that: Each letter is counted individually for replacement so if for example s[left..right] = "aaa", and k = 2, we can only replace two of the letters. (Also, note that the initial string s is never modified by any query.)

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.

Constraints:

  • 1 <= s.length, queries.length <= 10^5
  • 0 <= queries[i][0] <= queries[i][1] < s.length
  • 0 <= queries[i][2] <= s.length
  • s only contains lowercase English letters.

Solution

Use a map to store each index and the counts of the letters up to the index. The map contains s.length() entries, where each key is an index and each value is an array of length 26.

For each query in queries, obtain left = query[0], right = query[1] and k = query[2]. The counts of the letters in the substring can be obtained using keys left - 1 and right, where left - 1 is only necessary when left > 0.

Since the substring can be rearranged, the only thing to consider is the number of letters that have odd counts. For a substring, it is possible to be a palindrome string after the operations if and only if the number of letters that have odd counts divided by 2 (integer division) is less than or equal to k.

For each query in queries, return a boolean type result using the logic above, and add the result to the result list. Finally, return the result list.

  • class Solution {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        Map<Integer, int[]> countsMap = new HashMap<Integer, int[]>();
        int[] counts = new int[26];
        char c0 = s.charAt(0);
        counts[c0 - 'a']++;
        countsMap.put(0, counts);
        int length = s.length();
        for (int i = 1; i < length; i++) {
            int[] prevCounts = countsMap.get(i - 1);
            int[] curCounts = new int[26];
            System.arraycopy(prevCounts, 0, curCounts, 0, 26);
            char c = s.charAt(i);
            curCounts[c - 'a']++;
            countsMap.put(i, curCounts);
        }
        List<Boolean> booleanList = new ArrayList<Boolean>();
        for (int[] query : queries) {
            int left = query[0], right = query[1], k = query[2];
            boolean canMake = canMakePalindrome(countsMap, left, right, k);
            booleanList.add(canMake);
        }
        return booleanList;
    }

    public boolean canMakePalindrome(Map<Integer, int[]> countsMap, int left, int right, int k) {
        int[] counts = countsMap.get(right);
        int[] curCounts = new int[26];
        System.arraycopy(counts, 0, curCounts, 0, 26);
        if (left > 0) {
            int[] prevCounts = countsMap.get(left - 1);
            for (int i = 0; i < 26; i++)
                curCounts[i] -= prevCounts[i];
        }
        int oddCounts = 0;
        for (int i = 0; i < 26; i++) {
            if (curCounts[i] % 2 != 0)
                oddCounts++;
        }
        return oddCounts / 2 <= k;
    }
}

  • // OJ: https://leetcode.com/problems/can-make-palindrome-from-substring/
// Time: O(N + Q)
// Space: O(N)
class Solution {
public:
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& Q) {
        int N = s.size();
        vector<array<int, 26>> cnts(N);
        for (int i = 0; i < N; ++i) {
            if (i > 0) cnts[i] = cnts[i - 1];
            cnts[i][s[i] - 'a']++;
        }
        vector<bool> ans;
        for (auto &q : Q) {
            int from = q[0], to = q[1], k = q[2], odd = 0;
            auto cnt = cnts[to];
            if (from != 0) {
                for (int i = 0; i < 26; ++i) {
                    cnt[i] -= cnts[from - 1][i];
                }
            }
            for (int i = 0; i < 26; ++i) {
                odd += cnt[i] % 2;
            }
            ans.push_back(odd - 2 * k <= 1);
        }
        return ans;
    }
};

  • 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

############

# 1177. Can Make Palindrome from Substring
# https://leetcode.com/problems/can-make-palindrome-from-substring/

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        n = len(s)
        res = []
        dp = [[0] * 26]
        
        for i in range(1, n + 1):
            t = dp[i - 1][:]
            ch = ord(s[i - 1]) - ord('a')
            t[ch] += 1
            dp.append(t)
        
        
        for l,r,k in queries:
            left = dp[l]
            right = dp[r + 1]
            
            cnt = 0
            for i in range(26):
                cnt += (right[i] - left[i]) & 1
            
            res.append(cnt // 2 <= k)
        
        return res

All Problems

All Solutions