Problem

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.

Examples

Example 1:

1
2
3

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

Example 2:

1
2

Input: s = "12345678"
Output: 1

Example 3:

1
2
3

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

Solution

Method 1 - Using bitmask and hashmap

Here is the approach: To identify the length of the maximum awesome substring that can be made a palindrome by swapping characters in s, we need to leverage the properties of palindromes:

  1. Palindrome Properties:
    • A string is a palindrome if each character appears an even number of times, except for at most one character which can appear an odd number of times.
  2. Use Bitmasking:
    • Use a bitmask to represent the parity (odd/even) of character counts. This way, each bit in the bitmask corresponds to a character (a to z), indicating whether the character’s count is odd or even.
    • Compute the state (bitmask) as we iterate through the string. This helps track the parity of character counts up to each position.
  3. HashMap for Previous States:
    • Use a HashMap to store the first occurrence of each bitmask. This helps in quickly calculating the maximum length of substrings with specific properties.
    • If we encounter the same bitmask again, it means the characters in between can form a palindrome.
  4. Check for Single Odd Character:
    • Besides checking for exact bitmask parity, also check for each bit deviation to allow for one odd character (using mask ^ (1 << i)).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
    public int maxLengthAwesomeSubstring(String s) {
        Map<Integer, Integer> map = new HashMap<>();
        int mask = 0, ans = 0;
        map.put(0, -1);
        
        for (int i = 0; i < s.length(); i++) {
            mask ^= 1 << (s.charAt(i) - 'a');
            if (map.containsKey(mask)) {
                ans = Math.max(ans, i - map.get(mask));
            } else {
                map.put(mask, i);
            }

            for (int j = 0; j < 26; j++) {
                int temp_mask = mask ^ (1 << j);
                if (map.containsKey(temp_mask)) {
                    ans = Math.max(ans, i - map.get(temp_mask));
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def maxLengthAwesomeSubstring(self, s: str) -> int:
        map = {0: -1}
        mask = 0
        ans = 0
        
        for i, char in enumerate(s):
            mask ^= 1 << (ord(char) - ord('a'))
            if mask in map:
                ans = max(ans, i - map[mask])
            else:
                map[mask] = i
            
            for j in range(26):
                temp_mask = mask ^ (1 << j)
                if temp_mask in map:
                    ans = max(ans, i - map[temp_mask])
        
        return ans

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string s. Each character is processed once, updating and checking the bitmask.
  • 🧺 Space complexity: O(1) for the bitmask and auxiliary variables, but the HashMap can grow up to O(n) in the worst case.