Question

1542. Find Longest Awesome Substring

中文文档

Description

You are 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 a 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.

 

Constraints:

• 1 <= s.length <= 105
• s consists only of digits.

Solutions

Solution 1

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

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

class Solution {
public:
  int longestAwesome(string s) {
    vector<int> d(1024, -1);
    d[0] = 0;
    int st = 0, ans = 1;
    for (int i = 1; i <= s.size(); ++i) {
      int v = s[i - 1] - '0';
      st ^= 1 << v;
      if (~d[st]) {
        ans = max(ans, i - d[st]);
      } else {
        d[st] = i;
      }
      for (v = 0; v < 10; ++v) {
        if (~d[st ^ (1 << v)]) {
          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
}