Welcome to Subscribe On Youtube

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

1542. Find Longest Awesome Substring (Hard)

Given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it palindrome.

Return the length of the maximum length awesome substring of s.

 

Example 1:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2:

Input: s = "12345678"
Output: 1

Example 3:

Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

Example 4:

Input: s = "00"
Output: 2

 

Constraints:

  • 1 <= s.length <= 10^5
  • s consists only of digits.

Related Topics: String, Bit Manipulation

Solution 1.

  • class Solution {
        public int longestAwesome(String s) {
            if (s == null || s.length() == 0)
                return 0;
            Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
            int length = s.length();
            int[][] counts = new int[length][10];
            int digit0 = s.charAt(0) - '0';
            counts[0][digit0] = 1;
            int num0 = countsToNum(counts[0]);
            List<Integer> list0 = new ArrayList<Integer>();
            list0.add(0);
            map.put(num0, list0);
            for (int i = 1; i < length; i++) {
                int digit = s.charAt(i) - '0';
                for (int j = 0; j <= 9; j++)
                    counts[i][j] = counts[i - 1][j];
                counts[i][digit] = 1 - counts[i][digit];
                int num = countsToNum(counts[i]);
                List<Integer> list = map.getOrDefault(num, new ArrayList<Integer>());
                list.add(i);
                map.put(num, list);
            }
            int maxLength = 1;
            Set<Integer> visited = new HashSet<Integer>();
            for (int i = length - 1; i > 0; i--) {
                int num = countsToNum(counts[i]);
                if (num == 0 || (num & (num - 1)) == 0)
                    maxLength = Math.max(maxLength, i + 1);
                else if (visited.add(num)) {
                    int[] curCounts = new int[10];
                    System.arraycopy(counts[i], 0, curCounts, 0, 10);
                    List<Integer> list = map.get(num);
                    if (list.size() > 1)
                        maxLength = Math.max(maxLength, i - list.get(0));
                    for (int j = 0; j <= 9; j++) {
                        curCounts[j] = 1 - curCounts[j];
                        int newNum = countsToNum(curCounts);
                        if (map.containsKey(newNum)) {
                            List<Integer> newList = map.get(newNum);
                            maxLength = Math.max(maxLength, i - newList.get(0));
                        }
                        curCounts[j] = 1 - curCounts[j];
                    }
                }
            }
            return maxLength;
        }
    
        public int countsToNum(int[] counts) {
            int num = 0;
            int base = 1;
            int length = counts.length;
            for (int i = 0; i < length; i++) {
                num += counts[i] * base;
                base *= 2;
            }
            return num;
        }
    }
    
    ############
    
    class Solution {
        public int longestAwesome(String s) {
            int[] d = new int[1024];
            int st = 0, ans = 1;
            Arrays.fill(d, -1);
            d[0] = 0;
            for (int i = 1; i <= s.length(); ++i) {
                int v = s.charAt(i - 1) - '0';
                st ^= 1 << v;
                if (d[st] >= 0) {
                    ans = Math.max(ans, i - d[st]);
                } else {
                    d[st] = i;
                }
                for (v = 0; v < 10; ++v) {
                    if (d[st ^ (1 << v)] >= 0) {
                        ans = Math.max(ans, i - d[st ^ (1 << v)]);
                    }
                }
            }
            return ans;
        }
    }
    
  • // OJ: https://leetcode.com/problems/find-longest-awesome-substring/
    // Time: O(N)
    // Space: O(1) since there are at most 2^10=1024 states.
    class Solution {
    public:
        int longestAwesome(string s) {
            unordered_map<int, int> m{ {0,-1} }; // mask -> index of first occurrence
            int ans = 0;
            for (int i = 0, mask = 0; i < s.size(); ++i) {
                mask ^= 1 << (s[i] - '0');
                if (m.count(mask)) ans = max(ans, i - m[mask]);
                else m[mask] = i;
                for (int j = 0; j < 10; ++j) {
                    int prev = mask ^ (1 << j);
                    if (m.count(prev)) ans = max(ans, i - m[prev]);
                }
            }
            return ans;
        }
    };
    
  • class Solution:
        def longestAwesome(self, s: str) -> int:
            st = 0
            d = {0: -1}
            ans = 1
            for i, c in enumerate(s):
                v = int(c)
                st ^= 1 << v
                if st in d:
                    ans = max(ans, i - d[st])
                else:
                    d[st] = i
                for v in range(10):
                    if st ^ (1 << v) in d:
                        ans = max(ans, i - d[st ^ (1 << v)])
            return ans
    
    
    
  • func longestAwesome(s string) int {
    	d := [1024]int{}
    	d[0] = 1
    	st, ans := 0, 1
    	for i, c := range s {
    		i += 2
    		st ^= 1 << (c - '0')
    		if d[st] > 0 {
    			ans = max(ans, i-d[st])
    		} else {
    			d[st] = i
    		}
    		for v := 0; v < 10; v++ {
    			if d[st^(1<<v)] > 0 {
    				ans = max(ans, i-d[st^(1<<v)])
    			}
    		}
    	}
    	return ans
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions