What is the time complexity of Find Longest Awesome Substring?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Find Longest Awesome Substring?

This problem uses Hash Table, String, Bit Manipulation. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Find Longest Awesome Substring?

Insight 1: A substring is awesome if it can be rearranged to form a palindrome. This means at most one digit can appear an odd number of times. Insight 2: We can use a bitmask to represent the parity (even or odd) of the counts of each digit. Each bit in the mask corresponds to a digit (0-9). A bit is set to 1 if the count of that digit is odd, and 0 if it's even.

Which companies ask LeetCode 1542. Find Longest Awesome Substring in interviews?

This problem is frequently asked at Directi.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Find Longest Awesome Substring - LeetCode 1542 Solution

Find Longest Awesome Substring - Complete Solution Guide

Find Longest Awesome Substring is LeetCode problem 1542, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 sub

Detailed Explanation

The problem asks us to find the length of the longest substring of a given string 's' that can be rearranged to form a palindrome. Such a substring is called 'awesome'. The string 's' consists only of digits. A substring can be rearranged into a palindrome if and only if the count of each digit is even, or at most one digit has an odd count. The goal is to maximize the length of such a substring.

Solution Approach

The solution uses a prefix-based approach with a bitmask to keep track of the parity of each digit's count. It iterates through the string, updating the bitmask at each position. The algorithm maintains an array 'first_occurrence' to store the first index at which each mask occurs. By comparing the current mask with previously seen masks, we can determine if a substring is 'awesome' and update the maximum length accordingly.

Step-by-Step Algorithm

Step 1: Initialize an array 'first_occurrence' of size 1024 (2^10) with all elements set to the length of the string 'n'. This array will store the first index at which each bitmask is encountered. Initialize first_occurrence[0] to -1, since a mask of 0 (all counts even) occurs before the string starts.
Step 2: Initialize 'ans' (the maximum length) to 0 and 'mask' (the current bitmask) to 0.
Step 3: Iterate through the string 's' from left to right (index 'i').
Step 4: Update the current bitmask 'mask' by XORing it with (1 << digit), where 'digit' is the numeric value of the current character s[i]. This toggles the bit corresponding to the digit.
Step 5: Check if the current mask has been seen before. Calculate the length of the substring ending at the current index 'i' that has the same mask, which would be a perfect palindrome: `i - first_occurrence[mask]`. Update 'ans' to be the maximum of its current value and this length.
Step 6: Check if a mask differing by only one bit (i.e. one digit having an odd count) has been seen before. For each digit 'j' from 0 to 9, XOR 'mask' with (1 << j) to create a 'test_mask'. Calculate the length of the substring ending at the current index 'i' and having the test mask: `i - first_occurrence[test_mask]`. Update 'ans' to be the maximum of its current value and this length.
Step 7: If the current mask has not been seen before (i.e., first_occurrence[mask] is still equal to the initial value 'n'), update first_occurrence[mask] to the current index 'i'.
Step 8: After iterating through the entire string, return the value of 'ans'.

Key Insights

Insight 1: A substring is awesome if it can be rearranged to form a palindrome. This means at most one digit can appear an odd number of times.
Insight 2: We can use a bitmask to represent the parity (even or odd) of the counts of each digit. Each bit in the mask corresponds to a digit (0-9). A bit is set to 1 if the count of that digit is odd, and 0 if it's even.
Insight 3: If two prefixes have the same bitmask, the substring between them has all even counts, meaning it is a palindrome. If the masks differ by only one bit, then only that digit's count is odd. Therefore, those prefixes form an 'awesome' substring.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Hash Table, String, Bit Manipulation.

Companies

Asked at: Directi.

Find Longest Awesome Substring | LeetCode 1542

Hard

Hash Table String Bit Manipulation

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int longestAwesome(String s) {
        int n = s.length();
        
        int[] first_occurrence = new int[1024];
        for (int i = 0; i < 1024; i++) {
            first_occurrence[i] = n;
        }
        first_occurrence[0] = -1;
        
        int ans = 0;
        int mask = 0;
        
        for (int i = 0; i < n; i++) {
            int digit = Character.getNumericValue(s.charAt(i));
            mask ^= (1 << digit);
            
            ans = Math.max(ans, i - first_occurrence[mask]);
            
            for (int j = 0; j < 10; j++) {
                int test_mask = mask ^ (1 << j);
                ans = Math.max(ans, i - first_occurrence[test_mask]);
            }
            
            if (first_occurrence[mask] == n) {
                first_occurrence[mask] = i;
            }
        }
        
        return ans;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1542: Find Longest Awesome Substring - Detailed explanation and solution approaches.

Topics

Hash Table String Bit Manipulation

Companies

Directi

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:1542

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Initialize an array 'first_occurrence' of size 1024 (2^10) with all elements set to the length of the string 'n'. This array will store the first index at which each bitmask is encountered. Initialize first_occurrence[0] to -1, since a mask of 0 (all counts even) occurs before the string starts.
2
Step 2: Initialize 'ans' (the maximum length) to 0 and 'mask' (the current bitmask) to 0.
3
Step 3: Iterate through the string 's' from left to right (index 'i').
4
Step 4: Update the current bitmask 'mask' by XORing it with (1 << digit), where 'digit' is the numeric value of the current character s[i]. This toggles the bit corresponding to the digit.
5
Step 5: Check if the current mask has been seen before. Calculate the length of the substring ending at the current index 'i' that has the same mask, which would be a perfect palindrome: `i - first_occurrence[mask]`. Update 'ans' to be the maximum of its current value and this length.
6
Step 6: Check if a mask differing by only one bit (i.e. one digit having an odd count) has been seen before. For each digit 'j' from 0 to 9, XOR 'mask' with (1 << j) to create a 'test_mask'. Calculate the length of the substring ending at the current index 'i' and having the test mask: `i - first_occurrence[test_mask]`. Update 'ans' to be the maximum of its current value and this length.
7
Step 7: If the current mask has not been seen before (i.e., first_occurrence[mask] is still equal to the initial value 'n'), update first_occurrence[mask] to the current index 'i'.
8
Step 8: After iterating through the entire string, return the value of 'ans'.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is linear because we process each character of the string exactly once. The inner loop with 10 iterations is bounded by a constant, not by the length of input string. The space complexity is constant because the 'first_occurrence' array's size depends only on the number of possible bitmasks (2^10 = 1024), which is a constant, regardless of the size of input.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all possible substrings and check if each substring can be rearranged to form a palindrome. For each substring, count the occurrences of each digit and check if at most one digit has an odd count.

Time: O(n^3) where n is the length of the string. Generating all substrings takes O(n^2) time and checking if a substring is awesome takes O(n) time.Space: O(1). Constant extra space is used.

Trade-offs: This approach is simple to understand, but highly inefficient for larger input strings. It should not be used because it will lead to Time Limit Exceeded (TLE) error on LeetCode.

✨

Key Insights

1Insight 1: A substring is awesome if it can be rearranged to form a palindrome. This means at most one digit can appear an odd number of times.
2Insight 2: We can use a bitmask to represent the parity (even or odd) of the counts of each digit. Each bit in the mask corresponds to a digit (0-9). A bit is set to 1 if the count of that digit is odd, and 0 if it's even.
3Insight 3: If two prefixes have the same bitmask, the substring between them has all even counts, meaning it is a palindrome. If the masks differ by only one bit, then only that digit's count is odd. Therefore, those prefixes form an 'awesome' substring.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty String: Although not explicitly covered in the constraints (minimum length is 1), the solution implicitly handles it since the main loop wouldn't execute and initial value ans = 0 would be returned.
Edge case 2: String with all the same digits: For example, "11111". In this case, the bitmask will toggle between 0 and (1 << digit). The algorithm correctly finds the longest awesome substring.
Edge case 3: A single-character string: For example, "1". The mask will become (1 << 1). The first_occurrence array is initialized to n = 1. In the first iteration, ans = max(0, 0 - (-1)) = 1. first_occurrence[2] is set to 0. The code correctly returns 1.
Edge case 4: A string that is already a palindrome: For example "12321". The code identifies the whole string as an awesome substring.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not understanding the condition for a substring to be rearranged into a palindrome. It's crucial to remember that at most one digit can have an odd count.

✗Common mistake 2: Using a hash map to store counts of digits in each substring. While this is valid for the brute force approach, it's inefficient for this problem. The bitmask approach is much more efficient.

✗Common mistake 3: Forgetting to initialize first_occurrence[0] to -1. This is important because the empty prefix (before the start of the string) has a bitmask of 0, and we need to consider substrings starting from the beginning of the string.

✗Common mistake 4: Not initializing all values of 'first_occurrence' to 'n'. Failing to do so might result in using uninitialized values during the calculation, leading to incorrect results.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data compression: The bitmask technique can be used in lossless data compression algorithms to identify and represent repetitive patterns in data efficiently.

🏦Real-world scenario 2: Error detection and correction: Bitmasks can be used in communication protocols to detect and correct errors during data transmission. Parity checks, which involve ensuring that the number of 1s in a data unit is either even or odd, utilize bitmasking concepts.

🎮Real-world scenario 3: Bioinformatics: Determining longest subsequence satisfying some property can be useful for analyzing genomic sequences.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 11, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

❓

Frequently Asked Questions

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Find Longest Awesome Substring"?

For this hard-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?