Leetcode Problem 1520. Maximum Number of Non-Overlapping Substrings

1520. Maximum Number of Non-Overlapping Substrings

Leetcode Solutions

Greedy Approach with Two-Pass Scan

  1. Initialize two arrays to store the leftmost (left) and rightmost (right) indices for each character in the string.
  2. Perform a first pass through the string to populate the left and right arrays with the corresponding indices for each character.
  3. Initialize a list to store the valid substrings (validSubstrings).
  4. Perform a second pass through the string, starting from each character's leftmost index.
  5. For each starting index, attempt to form a valid substring by checking if all characters within the range have their leftmost occurrence at or after the starting index.
  6. If a valid substring is found, add it to the validSubstrings list with its ending index.
  7. Sort the validSubstrings list by the ending index in ascending order.
  8. Initialize a variable to keep track of the last selected substring's ending index (lastEnd).
  9. Iterate through the sorted validSubstrings list and select the non-overlapping substrings by comparing their starting indices with lastEnd.
  10. Update lastEnd to the ending index of the selected substring.
  11. Return the list of selected non-overlapping substrings.
UML Thumbnail

Interval Scheduling Maximization Approach

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...