Skip to content

String Suffix Array

Table of Contents

1163. Last Substring in Lexicographical Order

1754. Largest Merge Of Two Strings

2904. Shortest and Lexicographically Smallest Beautiful String

2904. Shortest and Lexicographically Smallest Beautiful String - Python Solution
# Sliding Window Variable Size
def shortestBeautifulSubstring(s: str, k: int) -> str:
    n = len(s)
    left = 0
    oneCount = 0
    minLen = float("inf")
    res = ""

    for right in range(n):
        if s[right] == "1":
            oneCount += 1

        while oneCount == k:
            size = right - left + 1

            if size < minLen:
                minLen = size
                res = s[left : right + 1]
            elif size == minLen:
                res = min(res, s[left : right + 1])

            if s[left] == "1":
                oneCount -= 1
            left += 1

    return res


s = "100011001"
k = 3
print(shortestBeautifulSubstring(s, k))  # 11001

3213. Construct String with Minimum Cost

1044. Longest Duplicate Substring

  • LeetCode | LeetCode CH (Hard)

  • Tags: string, binary search, sliding window, rolling hash, suffix array, hash function

718. Maximum Length of Repeated Subarray

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, binary search, dynamic programming, sliding window, rolling hash, hash function

718. Maximum Length of Repeated Subarray - Python Solution
from typing import List


def findLength(nums1: List[int], nums2: List[int]) -> int:
    m = len(nums1)
    n = len(nums2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    length = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if nums1[i - 1] == nums2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            if length < dp[i][j]:
                length = dp[i][j]

    return length


print(findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7]))  # 3

1923. Longest Common Subpath

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, rolling hash, suffix array, hash function

1408. String Matching in an Array

3076. Shortest Uncommon Substring in an Array

1316. Distinct Echo Substrings

3388. Count Beautiful Splits in an Array

2564. Substring XOR Queries

1698. Number of Distinct Substrings in a String

  • LeetCode | LeetCode CH (Medium)

  • Tags: string, trie, rolling hash, suffix array, hash function

1062. Longest Repeating Substring

  • LeetCode | LeetCode CH (Medium)

  • Tags: string, binary search, dynamic programming, rolling hash, suffix array, hash function

3135. Equalize Strings by Adding or Removing Characters at Ends

  • LeetCode | LeetCode CH (Medium)

  • Tags: string, binary search, dynamic programming, sliding window, hash function

Comments