1542. Find Longest Awesome Substring

HardBit ManipulationHash TableString
Leetcode Link

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

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

1class Solution:
2    def longestAwesome(self, s: str) -> int:
3        # Initialize the current state of the palindrome (bit mask representation of character counts)
4        current_state = 0
5        # Dictionary to store the earliest index of a particular state
6        state_index_map = {0: -1}
7        # Variable to store the length of the longest awesome substring
8        max_length = 1
9      
10        # Iterate over each character in the string along with its index
11        for index, char in enumerate(s):
12            digit = int(char)
13            # Flip the corresponding bit for the current digit
14            # This keeps track of odd/even counts of digits in the substring
15            current_state ^= 1 << digit
16          
17            # Check if this state occurred before to find a palindrome without a middle character
18            if current_state in state_index_map:
19                max_length = max(max_length, index - state_index_map[current_state])
20            else:
21                # Store the first occurrence of this state
22                state_index_map[current_state] = index
23          
24            # Check all possible states differing by 1 bit 
25            # (represents palindromes with one middle character)
26            for offset in range(10):
27                potential_state = current_state ^ (1 << offset)
28                if potential_state in state_index_map:
29                    max_length = max(max_length, index - state_index_map[potential_state])
30
31        # Return the length of the longest awesome substring found
32        return max_length
33
1class Solution {
2    public int longestAwesome(String s) {
3        // This array will keep track of the first appearance of a binary representation of st
4        int[] firstAppear = new int[1024];
5      
6        // Initialize array with -1 assuming that we haven't encountered any state yet
7        Arrays.fill(firstAppear, -1);
8      
9        // This is our status tracker; it will keep track of the count of each digit in the prefix
10        int currentState = 0;
11      
12        // Initialize the answer to be at least 1, as single digit is always awesome
13        int longestAwesomeLength = 1;
14      
15        // Set the starting state to 0, which makes an empty string awesome since there are even counts
16        firstAppear[0] = 0;
17      
18        // Iterate through each character of the string
19        for (int i = 1; i <= s.length(); i++) {
20            // Get the numeric value of the current character
21            int digitVal = s.charAt(i - 1) - '0';
22          
23            // Update currentState by toggling the bit at the digitVal position
24            currentState ^= 1 << digitVal;
25          
26            // Check if this state has occurred before
27            if (firstAppear[currentState] >= 0) {
28                // Calculate the length of the awesome substring and update the longestAwesomeLength
29                longestAwesomeLength = Math.max(longestAwesomeLength, i - firstAppear[currentState]);
30            } else {
31                // If haven't met this state, set the current position as the first appearance
32                firstAppear[currentState] = i;
33            }
34          
35            // Check all the states that differ by one digit flip (this represents at most one odd count digit)
36            for (int v = 0; v < 10; ++v) {
37                // If a similar state has been encountered before, compare and update the longestAwesomeLength
38                int analogousState = currentState ^ (1 << v);
39                if (firstAppear[analogousState] >= 0) {
40                    longestAwesomeLength = Math.max(longestAwesomeLength, i - firstAppear[analogousState]);
41                }
42            }
43        }
44      
45        // Return the length of the longest awesome substring
46        return longestAwesomeLength;
47    }
48}
49
1class Solution {
2public:
3    int longestAwesome(string s) {
4        // Create a vector to store the first occurrence index of each state
5        vector<int> firstOccurrenceIndex(1024, -1);
6        // Initialize the first occurrence of state 0 to index 0
7        firstOccurrenceIndex[0] = 0;
8        // This will keep track of the current state of digit frequency parity
9        int currentState = 0, maxLength = 1;
10        // Iterate over the string characters, 1-indexed
11        for (int i = 1; i <= s.size(); ++i) {
12            // Convert current character to integer
13            int digit = s[i - 1] - '0';
14            // Toggle the bit corresponding to the current digit to update parity state
15            currentState ^= 1 << digit;
16            // Check if we have seen this state before
17            if (firstOccurrenceIndex[currentState] != -1) {
18                // Calculate max length if the same state has been encountered before
19                maxLength = max(maxLength, i - firstOccurrenceIndex[currentState]);
20            } else {
21                // Record the first occurrence of this new state
22                firstOccurrenceIndex[currentState] = i;
23            }
24            // Check states that differ by one digit (flip each digit's parity)
25            for (digit = 0; digit < 10; ++digit) {
26                int toggledState = currentState ^ (1 << digit);
27                // Check if we have seen the toggled state before
28                if (firstOccurrenceIndex[toggledState] != -1) {
29                    // Calculate max length if the toggled state has been encountered before
30                    maxLength = max(maxLength, i - firstOccurrenceIndex[toggledState]);
31                }
32            }
33        }
34        // Return the maximum length of awesome substring found
35        return maxLength;
36    }
37};
38
1// This function calculates the longest awesome substring
2function longestAwesome(s: string): number {
3    // Create an array to store the first occurrence index of each state
4    const firstOccurrenceIndex: number[] = new Array(1024).fill(-1);
5    // Initialize the first occurrence of state 0 to index -1 to adjust for 0 indexing in the loop
6    firstOccurrenceIndex[0] = -1;
7    // This will keep track of the current state of digit frequency parity
8    let currentState: number = 0;
9    let maxLength: number = 1;
10
11    // Iterate over the string characters, 0-indexed
12    for (let i = 0; i < s.length; i++) {
13        // Convert current character to integer
14        const digit: number = parseInt(s[i], 10);
15        // Toggle the bit corresponding to the current digit to update parity state
16        currentState ^= 1 << digit;
17        // If we haven't seen this state, set the index, otherwise calculate max length
18        if (firstOccurrenceIndex[currentState] === -1) {
19            firstOccurrenceIndex[currentState] = i + 1; // Store the index +1 to adjust for the initial value of state 0
20        } else {
21            maxLength = Math.max(maxLength, i + 1 - firstOccurrenceIndex[currentState]);
22        }
23        // Check states that differ by one digit (flip each digit's parity)
24        for (let j = 0; j < 10; j++) {
25            const toggledState: number = currentState ^ (1 << j);
26            // If the toggled state has been seen, calculate max length
27            if (firstOccurrenceIndex[toggledState] !== -1) {
28                maxLength = Math.max(maxLength, i + 1 - firstOccurrenceIndex[toggledState]);
29            }
30        }
31    }
32    // Return the maximum length of the awesome substring found
33    return maxLength;
34}
35
36// Example usage:
37// const s: string = "3242415";
38// const result: number = longestAwesome(s);
39// console.log(result); // Outputs the length of the longest awesome substring
40

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.


Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄