LeetCode 3008: Find Beautiful Indices in the Given Array II Solution

Master LeetCode problem 3008 (Find Beautiful Indices in the Given Array II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3008. Find Beautiful Indices in the Given Array II

Hard

Two Pointers String Binary Search Rolling Hash String Matching Hash Function

Problem Explanation

Explanation

To solve this problem, we iterate through the string s and check for beautiful indices. For each index i, we check if the substring starting at i matches string a. If it does, we then check if there exists an index j such that the substring starting at j matches string b and the absolute difference between i and j is at most k. If these conditions are met, we add i to the result array.

Algorithm

Initialize an empty list beautifulIndices to store the beautiful indices.
Iterate over each index i in the range 0 to s.length - a.length.
Check if s.substring(i, i+a.length) is equal to string a.
If it is, iterate over each index j in the range max(0, i-k) to min(s.length - b.length, i+k).
Check if s.substring(j, j+b.length) is equal to string b and if abs(i-j) <= k.
If both conditions are met, add i to the beautifulIndices list.
Return the beautifulIndices list.

Time Complexity

The time complexity of this algorithm is O(n * m), where n is the length of string s and m is the maximum of the lengths of strings a and b.

Space Complexity

The space complexity of this algorithm is O(1) as we are not using any auxiliary data structures that grow with the input size.

Solution Code

class Solution {
    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
        List<Integer> beautifulIndices = new ArrayList<>();
        for (int i = 0; i <= s.length() - a.length(); i++) {
            if (s.substring(i, i + a.length()).equals(a)) {
                for (int j = Math.max(0, i - k); j <= Math.min(s.length() - b.length(), i + k); j++) {
                    if (s.substring(j, j + b.length()).equals(b) && Math.abs(i - j) <= k) {
                        beautifulIndices.add(i);
                        break;
                    }
                }
            }
        }
        return beautifulIndices;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3008 (Find Beautiful Indices in the Given Array II)?

This page provides optimized solutions for LeetCode problem 3008 (Find Beautiful Indices in the Given Array II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3008 (Find Beautiful Indices in the Given Array II)?

The time complexity for LeetCode 3008 (Find Beautiful Indices in the Given Array II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3008 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3008 in Java, C++, or Python.

Back to LeetCode Solutions