Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3303. Find Beautiful Indices in the Given Array II

My accepted Python solution to LeetCode problem 3303, Find Beautiful Indices in the Given Array II, running in 1921ms.

  • Difficulty: Hard
  • Python
  • Runtime 1921ms
  • Memory 68.5MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 1921ms, memory 68.5MB, accepted 2026-01-01.

python
class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        def z_function(s):
            n = len(s)
            z = [0] * n
            z[0] = n
            l, r = 0, 0
            for i in range(1, n):
                if i < r:
                    z[i] = min(r - i, z[i - l])
                while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                    z[i] += 1
                if i + z[i] > r:
                    l, r = i, i + z[i]
            return z
        
        def find_occurrences(text, pattern):
            combined = pattern + "#" + text
            z = z_function(combined)
            pattern_len = len(pattern)
            occurrences = []
            for i in range(pattern_len + 1, len(combined)):
                if z[i] >= pattern_len:
                    occurrences.append(i - pattern_len - 1)
            return occurrences
        
        a_indices = find_occurrences(s, a)
        b_indices = find_occurrences(s, b)
        
        if not a_indices or not b_indices:
            return []
        
        result = []
        j = 0
        for i in a_indices:
            while j < len(b_indices) and b_indices[j] < i - k:
                j += 1
            if j < len(b_indices) and abs(b_indices[j] - i) <= k:
                result.append(i)
        
        return result

Source