Find Longest Awesome Substring

Hard
1256.

Find Longest Awesome Substring

Find Longest Awesome Substring is a hard coding problem on strings, hash table and bit manipulation, asked in Amazon and Directi interviews.

s is a string of decimal digits. A non-empty substring of s is awesome if its digits can be rearranged (any number of swaps) into a palindrome.

Return the length of the longest awesome substring of s.

Example 1

Input
s = "2026"
Output
3
Explanation
`"202"` is already a palindrome; the whole string has two digits (0 and 6) with an odd count, so it cannot be rearranged into one.

Example 2

Input
s = "12345678"
Output
1
Explanation
No two equal digits exist, so only single characters work.

Example 3

Input
s = "1221331"
Output
7
Explanation
Only the digit 1 occurs an odd number of times, e.g. `"1323231"`.

Constraints

  • 1 <= s.length <= 10^5
  • s consists only of digits
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var longestAwesome = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Longest Awesome Substring — Problem & Solution

Find Longest Awesome Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Find Longest Awesome Substring is a hard coding problem on strings, hash table and bit manipulation, asked in Amazon and Directi interviews.

Problem statement

s is a string of decimal digits. A non-empty substring of s is awesome if its digits can be rearranged (any number of swaps) into a palindrome.

Return the length of the longest awesome substring of s.

Example 1

Input: s = "2026"
Output: 3
Explanation: `"202"` is already a palindrome; the whole string has two digits (0 and 6) with an odd count, so it cannot be rearranged into one.

Example 2

Input: s = "12345678"
Output: 1
Explanation: No two equal digits exist, so only single characters work.

Example 3

Input: s = "1221331"
Output: 7
Explanation: Only the digit 1 occurs an odd number of times, e.g. `"1323231"`.

Constraints

  • 1 <= s.length <= 10^5
  • s consists only of digits

Hints for Find Longest Awesome Substring

  1. Hint 1

    A multiset of characters can be arranged into a palindrome exactly when at most one character has an odd count.

  2. Hint 2

    Only the parity of each digit's count matters — ten bits. Compute the parity mask of every prefix.

  3. Hint 3

    The substring between prefixes i and j has parity mask mask[i] XOR mask[j]; it is awesome if that XOR is 0 or a single bit. Store the first index each mask occurs and, at every position, look up the current mask and its ten one-bit neighbours.

How to solve Find Longest Awesome Substring

Encode the odd/even count of each digit in a 10-bit prefix mask. A substring is awesome when the masks at its two ends differ in at most one bit, so remembering where each mask first appeared answers each position in eleven lookups.

Approach

  1. Keep first[mask], the earliest prefix length with that parity mask; set first[0] = 0 (the empty prefix) and mark the other 1,023 as unseen.
  2. Walk the string; after reading digit d at position j (1-based prefix length j), flip bit d of mask.
  3. If mask was seen before, the substring between is all-even: update the answer with j - first[mask].
  4. For each digit b, if mask ^ (1 << b) was seen, that substring has exactly one odd digit: update with j - first[mask ^ (1 << b)].
  5. If mask is new, record first[mask] = j. Return the best length.

Why it works

The count of digit d in s[i..j) is the difference of two prefix counts, so its parity is the XOR of the two prefix parities; the substring's parity mask is therefore mask[i] ^ mask[j]. A palindrome arrangement exists iff that mask has at most one set bit. For a fixed right end the longest such substring uses the earliest compatible left prefix, which is exactly what first stores.

Complexity

  • Time — O(10 · n)
  • Space — O(2^10)

Pitfalls

  • Recording a mask's index again when it reappears loses the earliest position — only set first the first time.
  • Forgetting the empty prefix (first[0] = 0) misses awesome substrings that start at index 0.
  • Checking only the all-even case misses the palindromes with one odd centre digit.

Reference solution

Python

def longestAwesome(s: str) -> int:
    first = [-1] * 1024
    first[0] = 0
    mask = 0
    best = 0
    for j, ch in enumerate(s, 1):
        mask ^= 1 << (ord(ch) - 48)
        if first[mask] >= 0:
            best = max(best, j - first[mask])
        for b in range(10):
            m = mask ^ (1 << b)
            if first[m] >= 0 and j - first[m] > best:
                best = j - first[m]
        if first[mask] < 0:
            first[mask] = j
    return best

Java

public static int longestAwesome(String s) {
    int[] first = new int[1024];
    Arrays.fill(first, -1);
    first[0] = 0;
    int mask = 0, best = 0;
    for (int j = 1; j <= s.length(); j++) {
        mask ^= 1 << (s.charAt(j - 1) - '0');
        if (first[mask] >= 0) best = Math.max(best, j - first[mask]);
        for (int b = 0; b < 10; b++) {
            int m = mask ^ (1 << b);
            if (first[m] >= 0 && j - first[m] > best) best = j - first[m];
        }
        if (first[mask] < 0) first[mask] = j;
    }
    return best;
}

C++

int longestAwesome(string s) {
    vector<int> first(1024, -1);
    first[0] = 0;
    int mask = 0, best = 0;
    for (int j = 1; j <= (int)s.size(); j++) {
        mask ^= 1 << (s[j - 1] - '0');
        if (first[mask] >= 0) best = max(best, j - first[mask]);
        for (int b = 0; b < 10; b++) {
            int m = mask ^ (1 << b);
            if (first[m] >= 0 && j - first[m] > best) best = j - first[m];
        }
        if (first[mask] < 0) first[mask] = j;
    }
    return best;
}

JavaScript

var longestAwesome = function(s) {
    var first = new Array(1024).fill(-1);
    first[0] = 0;
    var mask = 0, best = 0;
    for (var j = 1; j <= s.length; j++) {
        mask ^= 1 << (s.charCodeAt(j - 1) - 48);
        if (first[mask] >= 0) best = Math.max(best, j - first[mask]);
        for (var b = 0; b < 10; b++) {
            var m = mask ^ (1 << b);
            if (first[m] >= 0 && j - first[m] > best) best = j - first[m];
        }
        if (first[mask] < 0) first[mask] = j;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets