In this guide, you will get 1542. Find Longest Awesome Substring LeetCode Solution with the best time and space complexity. The solution to Find Longest Awesome Substring problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Longest Awesome Substring
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.
Complexity Analysis
Time Complexity: O(10n) = O(n)
Space Complexity: O(1024) = O(1)
1542. Find Longest Awesome Substring LeetCode Solution in C++
class Solution {
public:
int longestAwesome(string s) {
int ans = 0;
int prefix = 0; // the binary prefix
vector<int> prefixToIndex(1024, s.length());
prefixToIndex[0] = -1;
for (int i = 0; i < s.length(); ++i) {
prefix ^= 1 << s[i] - '0';
ans = max(ans, i - prefixToIndex[prefix]);
for (int j = 0; j < 10; ++j)
ans = max(ans, i - prefixToIndex[prefix ^ 1 << j]);
prefixToIndex[prefix] = min(prefixToIndex[prefix], i);
}
return ans;
}
}; /* code provided by PROGIEZ */
1542. Find Longest Awesome Substring LeetCode Solution in Java
class Solution {
public int longestAwesome(String s) {
int ans = 0;
int prefix = 0; // the binary prefix
int[] prefixToIndex = new int[1024];
Arrays.fill(prefixToIndex, s.length());
prefixToIndex[0] = -1;
for (int i = 0; i < s.length(); ++i) {
prefix ^= 1 << s.charAt(i) - '0';
ans = Math.max(ans, i - prefixToIndex[prefix]);
for (int j = 0; j < 10; ++j)
ans = Math.max(ans, i - prefixToIndex[prefix ^ 1 << j]);
prefixToIndex[prefix] = Math.min(prefixToIndex[prefix], i);
}
return ans;
}
} // code provided by PROGIEZ
1542. Find Longest Awesome Substring LeetCode Solution in Python
class Solution:
def longestAwesome(self, s: str) -> int:
ans = 0
prefix = 0 # the binary prefix
prefixToIndex = [len(s)] * 1024
prefixToIndex[0] = -1
for i, c in enumerate(s):
prefix ^= 1 << int(c)
ans = max(ans, i - prefixToIndex[prefix])
for j in range(10):
ans = max(ans, i - prefixToIndex[prefix ^ 1 << j])
prefixToIndex[prefix] = min(prefixToIndex[prefix], i)
return ans # code by PROGIEZ
