Find Longest Awesome Substring
HardPrompt
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: 1Example 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 <= 105sconsists only of digits.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach is the most straightforward and involves a brute-force check of every possible substring. For each substring, we perform a full count of its character frequencies to determine if it can be rearranged into a palindrome. A string can be rearranged into a palindrome if at most one of its characters appears an odd number of times.
Algorithm
- Initialize
maxLength = 0. - Use two nested loops with indices
iandjto generate all possible substringss.substring(i, j + 1). - For each substring, create a helper function or an inner block of code to check if it's 'awesome'.
- To check if a substring is awesome:
- Create a frequency array of size 10 for digits '0' through '9'.
- Iterate through the substring's characters to populate the frequency array.
- Count how many digits have an odd frequency.
- If the number of digits with odd frequencies is 0 or 1, the substring is awesome.
- If the current substring is awesome, update
maxLength = max(maxLength, j - i + 1). - After checking all substrings, return
maxLength.
Walkthrough
The algorithm iterates through all possible start and end points of a substring. For each substring generated, it calculates the frequency of each digit ('0'-'9'). Then, it counts how many of these digits have an odd frequency. If this count is less than or equal to one, the substring is deemed 'awesome', and we update our maximum length found so far. This process is repeated for all O(N^2) substrings.
class Solution { public int longestAwesome(String s) { int n = s.length(); int maxLength = 0; if (n == 0) return 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // Substring s[i..j] int[] freq = new int[10]; for (int k = i; k <= j; k++) { freq[s.charAt(k) - '0']++; } int oddCount = 0; for (int count : freq) { if (count % 2 != 0) { oddCount++; } } if (oddCount <= 1) { maxLength = Math.max(maxLength, j - i + 1); } } } return maxLength; }}Complexity
Time
O(N^3), where N is the length of the string `s`. There are O(N^2) substrings, and checking each substring of length L involves an O(L) scan. Since L can be up to N, the total complexity is cubic.
Space
O(1), as the frequency map for digits '0'-'9' requires a constant amount of space (an array of size 10).
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem for small input sizes.
Cons
Extremely inefficient due to its cubic time complexity.
Will not pass the time limits for the given constraints (N up to 10^5).
This approach improves upon the naive brute-force method by optimizing the frequency counting step. Instead of re-calculating the frequencies for every substring from scratch, we can maintain a running count. As we extend the substring by one character at a time, we update the frequency map and the count of digits with odd frequencies in constant time.
Algorithm
- Initialize
maxLength = 0. - Use an outer loop to iterate through each possible start index
iof a substring. - For each
i, initialize a frequency arrayfreqof size 10 and a variableoddCount = 0. - Start an inner loop for the end index
jfromiton-1. - In the inner loop, for each character
s[j], update its frequency infreq. - As you update the frequency, also update
oddCount. If the frequency of the current digit becomes odd, incrementoddCount; if it becomes even, decrementoddCount. - After updating, if
oddCount <= 1, it means the substrings[i..j]is awesome. UpdatemaxLength = max(maxLength, j - i + 1). - Return
maxLengthafter the loops complete.
Walkthrough
We iterate through all possible starting positions i. For each i, we iterate from j = i to the end of the string, effectively considering all substrings starting at i. We maintain a frequency count of digits for the current substring s[i..j]. When we move from j to j+1, we just update the count for the new character s[j+1]. This avoids the third loop of the naive approach, reducing the complexity.
class Solution { public int longestAwesome(String s) { int n = s.length(); int maxLength = 0; if (n == 0) return 0; for (int i = 0; i < n; i++) { int[] freq = new int[10]; int oddCount = 0; for (int j = i; j < n; j++) { int digit = s.charAt(j) - '0'; freq[digit]++; if (freq[digit] % 2 != 0) { oddCount++; } else { oddCount--; } if (oddCount <= 1) { maxLength = Math.max(maxLength, j - i + 1); } } } return maxLength; }}Complexity
Time
O(N^2), where N is the length of the string. The two nested loops dominate the runtime, and the work inside the inner loop is constant time.
Space
O(1), as the frequency map requires constant space.
Trade-offs
Pros
A significant improvement over the O(N^3) approach.
Still relatively easy to reason about.
Cons
Still too slow for the given constraints, leading to a Time Limit Exceeded error.
This is the most efficient approach, solving the problem in linear time. It leverages bitmasks to track the parity of digit counts and a hash map (or an array) to store the first occurrences of these parity states. This allows us to find the longest awesome substring in a single pass through the string.
Algorithm
- The core idea is that a string can form a palindrome if at most one of its character counts is odd.
- We can track the parity (even/odd) of counts of the 10 digits using a 10-bit integer mask. The
d-th bit is 1 if digitdhas an odd count, 0 otherwise. - The mask for a substring
s[i..j]can be found byprefix_mask[j] ^ prefix_mask[i-1]. - The problem then becomes finding two indices
iandjsuch that the XOR of their prefix masks is either 0 (all even counts) or a power of two (one odd count), while maximizingj-i. - We can solve this in one pass:
- Initialize an array
firstOccurrenceof size 1024 to store the first index seen for each mask. Initialize it with a value indicating 'not seen' (e.g., a value larger than any valid index). - Set
firstOccurrence[0] = -1to handle awesome prefixes correctly. - Initialize
mask = 0andmaxLength = 0. - Iterate through the string from
i = 0ton-1: a. Updatemaskby XORing with1 << (s.charAt(i) - '0'). b. Case 1 (Even Palindrome): Check ifmaskhas been seen before. IffirstOccurrence[mask]exists, it means the substring between that first occurrence andihas a mask of 0. UpdatemaxLength = max(maxLength, i - firstOccurrence[mask]). c. Case 2 (Odd Palindrome): For each digitdfrom 0 to 9, create atestMask = mask ^ (1 << d). IffirstOccurrence[testMask]exists, it means the substring has one odd count. UpdatemaxLength = max(maxLength, i - firstOccurrence[testMask]). d. If the currentmaskis seen for the first time, record its index:firstOccurrence[mask] = i. - Return
maxLength.
- Initialize an array
Walkthrough
We use a bitmask to represent the parity of the counts of digits '0'-'9' in a prefix of the string. A 10-bit integer is sufficient, where the i-th bit is 1 if the digit i has appeared an odd number of times, and 0 otherwise. The mask for a substring s[i..j] is simply the XOR of the prefix masks for s[0..j] and s[0..i-1].
A substring is awesome if its mask is either 0 (all even counts) or a power of 2 (one odd count). We iterate through the string, calculating the prefix mask at each position i. We use an array firstOccurrence to store the earliest index at which we've seen each mask. For each position i, we check for previously seen masks that would result in an awesome substring and update our maxLength accordingly.
import java.util.Arrays; class Solution { public int longestAwesome(String s) { int n = s.length(); // An array is faster than a HashMap. Size is 2^10 = 1024. int[] firstOccurrence = new int[1024]; // Initialize with a value larger than any possible index. Arrays.fill(firstOccurrence, n); int mask = 0; int maxLength = 0; // Base case for prefixes that are awesome themselves. // A mask of 0 at index -1 means a prefix of length i - (-1) = i + 1. firstOccurrence[0] = -1; for (int i = 0; i < n; i++) { // Update the mask with the current character's digit. mask ^= (1 << (s.charAt(i) - '0')); // Case 1: The substring has all characters with even counts. maxLength = Math.max(maxLength, i - firstOccurrence[mask]); // Case 2: The substring has one character with an odd count. for (int j = 0; j < 10; j++) { int testMask = mask ^ (1 << j); maxLength = Math.max(maxLength, i - firstOccurrence[testMask]); } // Store the first occurrence of the current mask if not already stored. if (firstOccurrence[mask] == n) { // Use n as the 'not found' value firstOccurrence[mask] = i; } } return maxLength; }}Complexity
Time
O(N), where N is the length of the string. We iterate through the string once. Inside the loop, we perform a constant number of operations (a fixed loop of 10 for checking one-bit-off masks).
Space
O(1). The space is dominated by the `firstOccurrence` array. Since there are `2^10 = 1024` possible masks, the space required is constant and does not depend on the input size N.
Trade-offs
Pros
Highly efficient with linear time complexity.
Optimal solution that passes for all given constraints.
Cons
The logic involving bitmasks and prefix states can be less intuitive to come up with compared to brute-force methods.
Solutions
Solution
class Solution {public int longestAwesome(String s) { int[] d = new int[1024]; int st = 0, ans = 1; Arrays.fill(d, -1); d[0] = 0; for (int i = 1; i <= s.length(); ++i) { int v = s.charAt(i - 1) - '0'; st ^= 1 << v; if (d[st] >= 0) { ans = Math.max(ans, i - d[st]); } else { d[st] = i; } for (v = 0; v < 10; ++v) { if (d[st ^ (1 << v)] >= 0) { ans = Math.max(ans, i - d[st ^ (1 << v)]); } } } return ans; }}class Solution {public: int longestAwesome(string s) { vector<int> d(1024, -1); d[0] = 0; int st = 0, ans = 1; for (int i = 1; i <= s.size(); ++i) { int v = s[i - 1] - '0'; st ^= 1 << v; if (~d[st]) { ans = max(ans, i - d[st]); } else { d[st] = i; } for (v = 0; v < 10; ++v) { if (~d[st ^ (1 << v)]) { ans = max(ans, i - d[st ^ (1 << v)]); } } } return ans; }};class Solution: def longestAwesome(self, s: str) -> int: st = 0 d = {0: - 1} ans = 1 for i, c in enumerate(s): v = int(c) st ^= 1 << v if st in d: ans = max(ans, i - d[st]) else: d[st] = i for v in range(10): if st ^ (1 << v) in d: ans = max(ans, i - d[st ^ (1 << v)]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.