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.

// 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} };
        int state = 0, ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            state ^= 1 << (s[i] - '0');
            if (m.count(state)) ans = max(ans, i - m[state]);
            for (int j = 0; j < 10; ++j) {
                int prev = state ^ (1 << j);
                if (m.count(prev)) ans = max(ans, i - m[prev]);
            }
            if (!m.count(state)) m[state] = i;
        }
        return ans;
    }
};

Since there are only 1024 states, we can also use vector<int> for the map.

// OJ: https://leetcode.com/problems/find-longest-awesome-substring/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int longestAwesome(string s) {
        int state = 0, ans = 0, N = s.size();
        vector<int> m(1024, N);
        m[0] = -1;
        for (int i = 0; i < s.size(); ++i) {
            state ^= 1 << (s[i] - '0');
            ans = max(ans, i - m[state]);
            for (int j = 0; j < 10; ++j) {
                ans = max(ans, i - m[state ^ (1 << j)]);
            }
            m[state] = min(m[state], i);
        }
        return ans;
    }
};

• Java
• C++
• Python

• 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;
      }
  }
  

• // 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
  
  
  

All Problems

All Solutions