{x}
blog image

Find Longest Awesome Substring

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.

Solution Explanation: Find Longest Awesome Substring

This problem asks to find the length of the longest "awesome" substring within a given string s. An "awesome" substring is defined as a substring that can be rearranged to form a palindrome. This means that at most one character can appear an odd number of times in the substring.

The optimal solution uses bit manipulation and a hash table (or dictionary) for efficient lookups.

Approach:

  1. Bitmask Representation: We use a 10-bit integer (st) to represent the parity of each digit (0-9) in the current prefix of the string. Each bit corresponds to a digit; a set bit (1) indicates an odd count of that digit, and an unset bit (0) indicates an even count.

  2. Hash Table: A hash table d stores the first index where each bitmask st is encountered. This allows us to quickly check if a substring is "awesome."

  3. Iteration and Update: The algorithm iterates through the string:

    • For each character, it updates the bitmask st by XORing it with 1 << digit (where digit is the integer value of the character). This efficiently toggles the bit corresponding to the character's digit.
    • It checks if the current bitmask st exists in d. If it does, the substring from d[st] to the current index is awesome (all digits have even counts).
    • It also checks if flipping a single bit in st (using XOR with 1 << v for each v from 0 to 9) results in a bitmask already in d. This accounts for the possibility of having one digit with an odd count.
    • The length of the longest awesome substring found so far (ans) is updated accordingly.

  4. Return Value: Finally, the function returns ans, the length of the longest awesome substring.

Time Complexity: O(n * 10), which simplifies to O(n). The outer loop iterates through the string once (O(n)). The inner loop iterates through 10 possible bit flips for each character.

Space Complexity: O(210) = O(1024), which is considered constant space because it's independent of the input string's length. The hash table stores a maximum of 1024 entries (all possible bitmasks).

Code Examples:

The code examples provided in the original response demonstrate the algorithm in several programming languages. They efficiently implement the bitmask and hash table approach, accurately tracking the longest awesome substring's length. Each example effectively mirrors the algorithm's logic described above. The slight variations are due to the syntax and library functions of each language, but the core concept remains consistent.

Note: The max function used across the examples is a standard library function for finding the maximum of two numbers, ensuring the algorithm maintains the longest awesome substring length found so far. The d array (or dictionary) initialization varies slightly, but the purpose remains the same – to store and retrieve the first index for each bitmask.