Find Longest Awesome Substring - Leetcode Solution

Problem Statement:

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 palindrome.

Return the length of the maximum length awesome substring of s.

Solution:

The Brute Force Approach: The brute force approach is to generate all the substrings of a given string S and check whether each substring is a palindrome or not. If the substring is a palindrome, then we need to check whether we can make any number of swaps in order to make it palindrome. If it is, then we update the length of the longest awesome substring that we have found so far. This approach takes O(n^3) time complexity as we need to generate all substrings and check if they are palindromes.

Optimized Approach:

To optimize the solution we need to observe that if the number of odd frequency characters is greater than 1, then the substring cannot be palindrome. So if the number of odd frequency characters is less than or equal to 1, then it can be swapped to make it palindrome.

We will use a bitmask approach to generate all the substrings of s and keep a track of the frequency of the characters that appear in that substring. We can then check if we can swap the characters to make it a palindrome. As there are only 10 digits, we can represent the frequency of each digit using a 10-bit binary string. If a bit at a position i is 1, then it means that the frequency of digit i is odd.

Let S be the input string, and let n be the length of the string. We can iterate over the string and calculate the frequency of characters for every substring. We can use the bitmask technique described above to obtain the binary representation of the frequency of the characters in the substring.

We keep a map of the frequency of the bit strings that we have seen so far. We add the bit string to the map if it is not already in it. We can then check if we have already seen the inverse of this bit string. If we have, then it means that we can use the characters in this substring to form a palindrome. We update the length of the longest awesome substring if necessary.

The time complexity of this approach is O(n). This is because we iterate over the string once, and for every substring, we perform constant time operations. The space complexity of the algorithm is also O(n), as we store the frequency count of every substring in a map.

Algorithm :

1. Initialize a frequency array f, with all the values set to zero.
2. We have to initialize an integer variable mask = 0.
3. Initialize a hashmap mp of type <int, int> to store the frequency of bitset and the odd frequency bitset. Initially the mp contains the value mp[0] = -1, that helps to track the start index of even substrings that are palindromic.
4. Start iterating through the input string S.
5. For each index i of the string, we have to convert the character into an integer using c - ‘0’.
6. Update the frequency count of this integer c into variable f.
7. Create a new bitmask called bitset and set each bit of bitset by checking the parity of the frequencies in f. The i-th bit is set to 1 if the i-th digit has an odd frequency in f, and 0 otherwise.
8. Check whether mp contains this bitset or not.
9. If it contains this bitset, this means that we have already seen this bitset before. Get the index of the last occurrence of this bitset and use it to update the length of the longest awesome substring.
10. Else, Insert this bitset into the hashmap mp with value as current index.
11. For each possible value of i, we calculate the inverse b of the bitmask b = bitset xor (2^n – 1)– This operation inverts all the bits of the bitset.
12. If mp contains this inverse bitmask b, this means that the substring from the last occurrence of the inverse bitmask b to the current index i is awesome. We then update the length of the longest awesome substring.
13. Return the length of the longest awesome substring.

Code:

class Solution { public: int longestAwesome(string s) { int n = s.size(); vector<int> f(10, 0); unordered_map<int, int> mp; mp[0] = -1; int longest = 0, mask = 0; for(int i=0; i<n; i++){ int c = s[i] - '0'; f[c]++; mask ^= (1 << c); if(mp.count(mask)){ int j = mp[mask]; longest = max(longest, i-j); } for(int j=0; j<10; j++){ int b = mask^(1<<j); if(mp.count(b)){ int k = mp[b]; longest = max(longest, i-k); } } if(!mp.count(mask)) mp[mask] = i; } return longest; } };

Note:

1. C++ STL bitset can also be used to implement this algorithm for a bitmask approach.
2. We also need to handle edge cases when the given input string is all the same characters, and also if the input string is empty.

1