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

# 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 | 力扣

  • Tags: String, Binary Search, Sliding Window, Rolling Hash, Suffix Array, Hash Function

718. Maximum Length of Repeated Subarray

  • LeetCode | 力扣

  • Tags: Array, Binary Search, Dynamic Programming, Sliding Window, Rolling Hash, Hash Function

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

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

1062. Longest Repeating Substring

  • LeetCode | 力扣

  • Tags: String, Binary Search, Dynamic Programming, Rolling Hash, Suffix Array, Hash Function

3135. Equalize Strings by Adding or Removing Characters at Ends

Comments