LeetCode 1542: Find Longest Awesome Substring Solution

Master LeetCode problem 1542 (Find Longest Awesome Substring), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1542. Find Longest Awesome Substring

Hard

Hash Table String Bit Manipulation

Problem Explanation

Explanation:

To solve this problem, we can use bit manipulation to keep track of the parity of each digit in the substring. If a palindrome can be formed with the given substring, then the count of each digit's parity should be either even or odd, except for at most one digit whose count can be odd.

We can keep track of the parity of each digit using a bitmask. If the count of a digit is even, we clear the corresponding bit in the bitmask. If the count is odd, we set the bit. We can use a hashmap to store the bitmask and the index where it was last seen.

At each index, we update the bitmask based on the parity of the current digit and check if there exists a previous index where the bitmask differs by at most one bit. If such an index exists, we can form a palindrome substring by swapping some characters.

We initialize the hashmap with a bitmask of 0 at index -1 to handle the case where the awesome substring starts from index 0.

Solution Code

class Solution {
    public int longestAwesome(String s) {
        int n = s.length();
        int res = 0;
        int mask = 0;
        int[] seen = new int[1024];
        Arrays.fill(seen, n);
        seen[0] = -1;

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            mask ^= 1 << (c - '0');

            for (int j = 0; j < 10; j++) {
                int key = mask ^ (1 << j);
                res = Math.max(res, i - seen[key]);
            }
            res = Math.max(res, i - seen[mask]);

            seen[mask] = Math.min(seen[mask], i);
        }

        return res;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1542 (Find Longest Awesome Substring)?

This page provides optimized solutions for LeetCode problem 1542 (Find Longest Awesome Substring) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1542 (Find Longest Awesome Substring)?

The time complexity for LeetCode 1542 (Find Longest Awesome Substring) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1542 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1542 in Java, C++, or Python.

Back to LeetCode Solutions