We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Longest Awesome Substring

Number: 1668

Difficulty: Hard

Paid? No

Companies: Google, Directi

Problem Description

Given a string s consisting of digits, an "awesome" substring is a non-empty substring that can be rearranged (via swaps) to form a palindrome. The task is to return the length of the longest substring of s that is awesome.

Key Insights

  • A string can be rearranged into a palindrome if at most one digit has an odd frequency.
  • Use a bitmask to track the parity (even/odd count) of digits where the i-th bit corresponds to the digit i.
  • A substring's parity state can be computed using a prefix XOR technique.
  • If two prefix states are the same, the substring between them has even counts for all digits.
  • Additionally, flipping one bit in the current state represents a valid condition for one odd-count digit.
  • Maintain a dictionary that maps each bitmask state to its first occurrence index to efficiently compute the length of valid substrings.

Space and Time Complexity

Time Complexity: O(n * D) where n is the length of s and D is the number of digits (constant 10), effectively O(n).
Space Complexity: O(2^D) which is O(1024) ~ O(1) constant space usage with respect to n.

Solution

We compute the prefix bitmask where each bit (0-9) is toggled whenever a digit is encountered. For the current position:

  1. If the bitmask has been seen before, then the substring between the first occurrence and the current position is a candidate.
  2. Check for all possible variations by toggling each of the 10 bits from the current bitmask to account for one odd frequency digit.
  3. Update the maximum length accordingly.

We use a hash table (dictionary) to store the first index at which each bitmask state appears. This allows quickly computing substring lengths.

Code Solutions

# Python solution
def longestAwesome(s: str) -> int:
    # Dictionary to store first occurrence index of a given bitmask state
    state_index = {0: -1}  # initial state before any character is processed
    max_length = 0
    current_state = 0

    for idx, char in enumerate(s):
        # Toggle the bit corresponding to the digit
        digit = int(char)
        current_state ^= (1 << digit)
        
        # If current state seen before, update max length using this substring
        if current_state in state_index:
            max_length = max(max_length, idx - state_index[current_state])
        else:
            # Record first occurrence of current state
            state_index[current_state] = idx
        
        # Check for each possible one bit difference (allow one odd frequency)
        for j in range(10):
            toggled_state = current_state ^ (1 << j)
            if toggled_state in state_index:
                max_length = max(max_length, idx - state_index[toggled_state])
    
    return max_length

# Example usage:
print(longestAwesome("3242415"))  # Output: 5
← Back to All Questions