Find Longest Awesome Substring – LeetCode

This is the third question of our AlgoMaster Sheet from Hashing Section. In this question we are using a HashMap to store the the bit mask of the while traversing the array. For further clarification of the question and algorithm you can check out the AlgoMaster series.

Problem Statement

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.

Intuition:

As per the question, the only characters that are present inside the string are digits, So the range of the values lies from 0 to 9. In case of a string to satisfy the condition for the palindrome, It needs to fulfill either of the two conditions – All the characters appear an even number of times or All the characters appear an even number of times with exactly one character appearing an odd number of times. So in this case we can use a bitmask to find whether the digit appears even or odd a number of times.

In order to store the frequency in bitmask format we flip the i-th bit, where i is the digit present in the string. In this case, if the digit appears an even number of times then the bit at the respected position will be 0 (not set) and if it appears an odd number of times then it will be 1 (set).

We can use the HashMap to store the previously occurred bit arrangement. There are two conditions in which we need to calculate the length: First, if a current bit arrangement has occurred previously, and second if the current arrangement after flipping one bit has occurred previously. In this way the maximum of such substrings are calculated.

Algorithm:-

1. Declare a Map to store the bitmask and their indexes
2. While traversing the string, the bit in the digit-th position is flipped
3. If the bitmask is present in the Map, we calculate length by i – map[bitmask]
4. We store the maximum length as answer
5. Now we run a loop from 0 to 9 and we create a newMask by flipping one bit
6. If the newMask is present in the Map, we calculate length by i – map[newMask]
7. We again store the maximum length
8. We return the answer which is the maximum of the length

Code:-

class Solution {
public:
    int longestAwesome(string s) {
        unordered_map<int,int> map;  //Map to store previous occured number (bit arrangement)
        int l = s.size();  //To store the length of given string
        int bitmask = 0;
        int ans = 0;

        map[bitmask] = -1;  //To avoid edge cases in case of whole string is covered
        for(int i = 0 ; i < l ; i++)
        {
            int chr = s[i] - '0' ;
            bitmask = bitmask ^ ( 1 << chr ); // Flipping the bit at the chr position

            if(map.find(bitmask)!=map.end())  // If we encounter a bit arrangement previously we find the length
            {
                int length = i - map[bitmask] ;
                ans = max(ans,length);   // Updating the answer in case it is greater than current answer
            }
            else
                map[bitmask] = i;
            
            for(int pos=0 ; pos<10 ; pos++)
            {
                int newMask = bitmask ^ ( 1 << pos ); // Flipping one bit of the mask (In palindrome one digit can have odd number of occurence)
                
                if(map.find(newMask)!=map.end()) //If the new bit is previously present then we update the answer accordingly
                {
                    int length = i - map[newMask];
                    ans = max(ans,length);
                }
            }
        }
        return ans;
    }
};

class Solution {
    public int longestAwesome(String s) {
        HashMap<Integer,Integer> map = new HashMap<>();  //Map to store the previous occurence of bit arrangement
        int l = s.length();
        int bitmask = 0;
        int ans = 0;

        map.put(bitmask,-1);  //To avoid edge cases
        for(int i=0; i<l; i++)
        {
            int chr = s.charAt(i) - '0';
            bitmask = bitmask ^ ( 1 << chr ); //Flipping the bit at the chr position of the bitmask

            if(map.containsKey(bitmask)) //If the bit arrangement occur previously we find the length
            {
                int length = i - map.get(bitmask);
                ans = Math.max(ans,length);  // Updating the answer if length is greater than answer
            }
            else
                map.put(bitmask,i);
            
            for(int pos=0; pos<10; pos++) 
            {
                int newMask = bitmask ^ ( 1 << pos );  // Flipping one bit of the mask (In palindrome one digit can have odd number of occurence)
                
                if(map.containsKey(newMask)) //If the new bit arrangement occur previously we find the length
                {
                    int length = i - map.get(newMask);
                    ans = Math.max(ans,length);  // Updating the answer if new length is more than answer
                }
            }
        }
        return ans;
    }
}

Analysis of Time & Space Complexity:-

In this problem, we are using an always simple iterating over the string once. While we are also making 10 new mask for each iteration. So the Time Complexity is O (10 * N). We do not consider the numerical value in the case of Big O Notation, thus our Time Complexity is O(N). Also, we are using a map to store the previous occurrence of the bits so the Space Complexity is O(N).

If you have still any more doubts, make sure to check the following video by SUNYUL HOSSEN and also follow his YouTube Channel – CS FOR ALL for such amazing content!! For any questions, regarding the post, you can post down in the comment section!!

Contributors: Arghya Chatterjee: LinkedIn, Tanmay Dutta: LinkedIn, Raj Chowdhury: LinkedIn & Arjan Hazra: LinkedIn