1542. Find Longest Awesome Substring

Problem Description

The problem involves finding the longest "awesome" substring within the given string s. An "awesome" substring is defined as a substring that can be transformed into a palindrome through a series of character swaps. In other words, you can take some characters in the substring and swap them with others to form a palindrome.

A palindrome is a string that reads the same forwards and backwards, like "racecar" or "level". Therefore, for a substring to be awesome and potentially become a palindrome, it must have at most one character that appears an odd number of times. All other characters must appear an even number of times, so they can be mirrored around the central character.

The goal is to find the length of the longest possible awesome substring.

Intuition

To solve this problem, one key observation must be made: a palindrome has a symmetric structure, which means if you split it in the middle, one side is the reverse of the other. In a palindrome, all characters occur an even number of times, except for potentially one character (in the middle of an odd-length palindrome), which occurs an odd number of times.

The solution approach utilizes bitmasks to represent the count of characters modulo 2 (even or odd). The state transitions occur as we iterate through the string and toggle bits for the respective numeric values of characters.

Here's the intuition breakdown for the solution:

• Create a bitmask st (of 10 bits, one for each digit 0-9) that represents which numbers have occurred an odd number of times as we iterate over the string.
• Use a dictionary d to store the first index where each bitmask state occurs. Initializing the dictionary with {0: -1} handles the case where an "awesome" substring starts at the beginning of s.
• The solution iterates through s, and at each iteration, it toggles the bit that corresponds to the current character using XOR operation (st ^= 1 << v).
• If the current state of st exists in the dictionary d, it indicates a palindrome from the index d[st] to the current index i.
• The solution keeps track of the maximum length of an "awesome" substring found so far.
• Additionally, it checks if changing the current state of st by toggling each bit (from 0-9) leads to a state present in the dictionary which means a single character swap might form an awesome substring. If this check finds a longer substring, it updates the maximum length accordingly.
• After completing the loop, the maximum length found is returned as the length of the longest "awesome" substring.

This approach allows us to solve the problem with an O(n) time complexity, since it iterates through the string once and does a constant amount of work for each character.

Solution Approach

The implementation of the solution makes use of bitwise operations, hash tables (dictionaries in Python), and the understanding of palindrome properties.

Here's a step-by-step explanation of the algorithm by referring to the code above:

1. Initialize st to 0. This is a bitmask that will keep track of the parity (even or odd) of the counts of digits in the current substring. For example, if the third bit in st is 1, it means the digit 2 has appeared an odd number of times so far.

2. Initialize a dictionary d with a single key-value pair {0: -1}. The dictionary will map the state of st to the earliest index where this state was seen. The value -1 is used to handle cases where a palindrome starts from index 0.

3. Initialize ans to 1, since the minimum length of an awesome substring is 1 (a single digit is always a palindrome).

4. Iterate over the given string s, using enumerate to have both index i and character c in the loop. Convert the current character to an integer v.

5. Toggle the bit in the st bitmask corresponding to v. This is done with the XOR operator ^ and the bitwise left shift operator <<.

6. Check if this new state of st has been seen before. If it has, calculate the length of the substring from the first occurrence of this state to the current index i. This is a potential palindrome, so update ans if this length is larger than the current ans.

7. Additionally, loop through all digit positions from 0 to 9. Toggle each bit in the st bitmask to simulate having one character with an odd count (potential middle character in a palindrome). Check if this modified state has been seen before. If it has, it means that there exists a substring ending at the current index that could form an awesome substring with one swap. Update ans if a longer substring is found.

8. After the loop ends, return ans. This represents the length of the longest awesome substring found.

This solution cleverly utilizes bitmasks to track the parity of digit occurrences and a dictionary to remember first occurrences of bitmask states. The power of bitwise operations allows us to efficiently simulate all possible single-digit changes that may lead to a palindrome. The algorithm runs in O(n) time complexity with O(1) space complexity, as there are at most 2^10 possible bitmask states, which is a constant.

Example Walkthrough

Let us consider an example string s = "3242415" to illustrate the solution approach.

1. Initialize the bitmask st to 0. The bits in st will eventually correspond to the parity of the counts of each digit in the current substring.

2. Initialize the dictionary d with {0: -1}. It maps the parity state to the index where it was first encountered. The -1 handles cases where a palindrome starts at the first character of the string.

3. Initialize the answer ans to 1. Any single digit is trivially a palindrome.

4. Begin iterating over each character in the string s:

   • At index 0, the character is 3. Convert 3 to an integer and toggle the 3rd bit of st, making it 001000. Since this state has not been seen, add d[001000] = 0.
   • At index 1, the character is 2. Toggle the 2nd bit of st, making it 001100. Add d[001100] = 1 as this state is new.
   • At index 2, the character is 4. Toggle the 4th bit of st, making it 011100. This state has not been seen before, so add d[011100] = 2.
   • At index 3, the character is 2. Toggle the 2nd bit of st, reverting it to 010000. This state is new, add d[010000] = 3.
   • At index 4, the character is 4. Toggle the 4th bit of st, reverting it back to 000000. This is the first time encountering a state of all even counts, but it indicates a substring 32424 that is a palindrome and can be mirrored. The length is 5, so we update ans to 5.
   • At index 5, the character is 1. Toggle the 1st bit of st, making it 000001. Add d[000001] = 5, as this is a new state.
   • At index 6, the character is 5. Toggle the 5th bit of st, making it 000101. This state is new, so add d[000101] = 6.

5. Now, suppose we're at index 6. For each digit from 0-9, we consider toggling each bit of the current st (000101) one by one and look it up in the dictionary d. The only interesting toggles are 001101 and 000001 because these states have been encountered earlier, which means there's a palindrome 324241 and 5 when 5 or 1 is the middle character. The lengths are 6 and 1, respectively. The longest length is the one for 324241, which does not surpass our current ans of 5.

6. Continue this process until the end of the string, always updating ans to the maximum length found.

7. After completing the loop, the maximum value of ans remains 5, which is the length of the longest-awesome substring in s, and that substring is 32424.

By following the detailed solution approach using bitwise representation and a hash table, we efficiently found the longest awesome substring in our example.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the loops and the operations within them. There is a single loop running through the length of the string s. Inside the loop, the code performs a constant-time bitwise operation and checks for existence in a dictionary, which is generally considered to be O(1). Additionally, there is another loop within the main loop that iterates 10 times (constant) for each character in the string.

Thus, the overall time complexity is O(n) for the main loop multiplied by O(1) for operations within the loop and O(1) for dictionary lookup. Then, for every character, we loop a constant 10 times (assuming the cost of each iteration is constant), which does not change the linear time complexity.

Therefore, the total time complexity can be represented as O(n).

Space Complexity

The space complexity is primarily due to the dictionary d which is used to store the previous encounter of a certain state of st. In the worst case, this dictionary can have an entry for each unique state st produces. Since st represents a bitmask of at most 10 digits (representing 10 different digits in the string), there can be at most 2^10 different states. Additionally, the integer st and variable ans are of constant size.

Hence, the space complexity is O(1) for the constant variables and O(2^10) for the dictionary, regardless of the size of the input string. Since 2^10 is a constant number (1024), this can also be considered constant space in the context of big O notation: O(1).

Therefore, we can conclude that the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.