Leetcode Problem 1542. Find Longest Awesome Substring

1542. Find Longest Awesome Substring

Leetcode Solutions

Bitmasking and Prefix Sum Array Approach

  1. Initialize a prefix sum array dp with size 1024 (2^10 for 10 digits) and fill it with a large number (size of the string), except for dp[0] which should be set to -1.
  2. Initialize variables res for the result and mask for the current bitmask.
  3. Iterate through each character in the string: a. Update the mask by toggling the bit corresponding to the current digit. b. Update the result res with the maximum of the current result and the difference between the current index and the first occurrence of this mask in dp. c. For each digit from 0 to 9, toggle the corresponding bit in the mask and update the result res if we find a longer awesome substring. d. Update dp[mask] with the minimum of the current index and the existing value in dp[mask].
  4. Return the result res.
UML Thumbnail

Brute Force Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...