2002. Maximum Product of the Length of Two Palindromic Subsequences - Medium

前往題目

思路

Brute force

1. 循環把所有mask都走過一遍，有Match就保留
2. 只留下是palindrome的
3. 嵌套疊代，把兩個match的mask計算長度，放入結果，取最大值

這題用mask，比較難一下就看懂在幹麻

Code

class Solution {
    public int maxProduct(String s) {
        int n = s.length();
        // bitmask : length
        HashMap<Integer, Integer> map = new HashMap<>();

        // Go through all the possible masks
        for (int mask = 1; mask < (1 << n); ++mask) {
            StringBuilder subseq = new StringBuilder("");

            // 
            for (int i = 0; i < n; ++i) {
                // if matched
                if ((mask & 1 << i) > 0) {
                    subseq.append(s.charAt(i));
                }
            }

            if (isPalin(subseq.toString())) {
                map.put(mask, subseq.length());
            }
        }

        int res = 0;

        for (int mask1 : map.keySet()) {
            for (int mask2 : map.keySet()) {
                if ((mask1 & mask2) == 0) {
                    res = Math.max(res, map.get(mask1) * map.get(mask2));
                }
            }
        }

        return res;
    }

    private boolean isPalin(String s) {
        int l = 0, r = s.length() - 1;

        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            ++l;
            --r;
        }
        return true;
    }
}