What is the time complexity of Find Beautiful Indices in the Given Array II?

The optimal solution has a time complexity of O(n*m + n*l + len(indices_a)*len(indices_b)).

What is the space complexity of Find Beautiful Indices in the Given Array II?

The space complexity is O(n + m + l).

What data structures are used to solve Find Beautiful Indices in the Given Array II?

This problem uses Two Pointers, String, Binary Search, Rolling Hash, String Matching, Hash Function. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Find Beautiful Indices in the Given Array II?

Insight 1: Efficient String Matching: The core of the problem involves finding all occurrences of substrings `a` and `b` within `s`. A naive approach of comparing every possible substring would be inefficient, leading to a higher time complexity. Thus KMP Algorithm must be used. Insight 2: Two-Pointer Optimization: After identifying the indices of occurrences of `a` and `b`, the problem requires finding pairs of indices `i` and `j` within a specified distance `k`. A brute-force approach would be inefficient. The efficient approach uses the sorted indices of 'b' to quickly check the 'k' distance constraint.

Which companies ask LeetCode 3008. Find Beautiful Indices in the Given Array II in interviews?

This problem is frequently asked at Palantir Technologies, PhonePe.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

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

Q: How to solve Find Beautiful Indices in the Given Array II?

The provided solutions utilize the Knuth-Morris-Pratt (KMP) algorithm to efficiently find all occurrences of strings `a` and `b` within string `s`. Then, it iterates through the occurrences of `a`, and for each occurrence, it uses a two-pointer technique to check if there exists an occurrence of `b` within the distance `k`. If a matching occurrence of `b` is found within the distance `k`, the index `i` is added to the result.

Find Beautiful Indices in the Given Array II - Complete Solution Guide

Find Beautiful Indices in the Given Array II is LeetCode problem 3008, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given a 0-indexed string s , a string a , a string b , and an integer k . An index i is beautiful if: 0 <= i <= s.length - a.length s[i..(i + a.length - 1)] == a There exists an index j such that: 0 <= j <= s.length - b.length s[j..(j + b.length - 1)] == b |j - i| <= k Return the array that contains beautiful indices in sorted order from smallest to largest . Example 1: Input: s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15 Output: [16,33] Explanation: There a

Detailed Explanation

The problem asks us to find all "beautiful" indices in a given string `s`. An index `i` is considered beautiful if the substring of `s` starting at `i` matches string `a`, and there exists another index `j` such that the substring of `s` starting at `j` matches string `b`, and the absolute difference between `i` and `j` is less than or equal to `k`. The goal is to return a sorted list of all such beautiful indices.

Solution Approach

The provided solutions utilize the Knuth-Morris-Pratt (KMP) algorithm to efficiently find all occurrences of strings `a` and `b` within string `s`. Then, it iterates through the occurrences of `a`, and for each occurrence, it uses a two-pointer technique to check if there exists an occurrence of `b` within the distance `k`. If a matching occurrence of `b` is found within the distance `k`, the index `i` is added to the result.

Step-by-Step Algorithm

Step 1: Implement KMP Search: Implement the KMP algorithm to find all starting indices where string `a` appears in string `s` and store these indices in a list called `indices_a`. Repeat the same process for string `b`, storing the indices in `indices_b`.
Step 2: Handle Empty Cases: If either `indices_a` or `indices_b` is empty, then no beautiful indices exist, and return an empty list.
Step 3: Iterate through 'a' indices and find valid 'b' indices: Iterate through each index `i` in `indices_a`. For each `i`, use a second pointer (`j_ptr`) to find an index `j` in `indices_b` such that `|i - j| <= k`.
Step 4: Two-Pointer Optimization for 'b' index search: Increment `j_ptr` until `indices_b[j_ptr]` is greater than or equal to `i - k`. If `j_ptr` reaches the end of `indices_b` or if `indices_b[j_ptr]` is greater than `i + k`, then there is no suitable `j` in `indices_b` for the current `i`.
Step 5: Check the 'k' distance constraint: If `j_ptr` is within the bounds of `indices_b` and `indices_b[j_ptr]` is less than or equal to `i + k`, then the 'k' distance condition is met, and `i` is a beautiful index. Add it to result.
Step 6: Return Result: After iterating through all indices in `indices_a`, return the sorted list of beautiful indices.

Key Insights

Insight 1: Efficient String Matching: The core of the problem involves finding all occurrences of substrings `a` and `b` within `s`. A naive approach of comparing every possible substring would be inefficient, leading to a higher time complexity. Thus KMP Algorithm must be used.
Insight 2: Two-Pointer Optimization: After identifying the indices of occurrences of `a` and `b`, the problem requires finding pairs of indices `i` and `j` within a specified distance `k`. A brute-force approach would be inefficient. The efficient approach uses the sorted indices of 'b' to quickly check the 'k' distance constraint.
Insight 3: Handling Empty Result: Pay attention to the edge cases where no occurrences of `a` or `b` are found in `s`. In this situation, the function must return an empty list.

Complexity Analysis

Time Complexity: O(n*m + n*l + len(indices_a)*len(indices_b))

Space Complexity: O(n + m + l)

Topics

This problem involves: Two Pointers, String, Binary Search, Rolling Hash, String Matching, Hash Function.

Companies

Asked at: Palantir Technologies, PhonePe.

Find Beautiful Indices in the Given Array II | LeetCode 3008

Hard

Two Pointers String Binary Search Rolling Hash String Matching Hash Function

Time: O(n*m + n*l + len(indices_a)*len(indices_b))Space: O(n + m + l)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
        List<Integer> indices_a = kmp_search(s, a);
        List<Integer> indices_b = kmp_search(s, b);

        if (indices_a == null || indices_a.isEmpty() || indices_b == null || indices_b.isEmpty()) {
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        int j_ptr = 0;

        for (int i : indices_a) {
            while (j_ptr < indices_b.size() && indices_b.get(j_ptr) < i - k) {
                j_ptr++;
            }

            if (j_ptr < indices_b.size() && indices_b.get(j_ptr) <= i + k) {
                result.add(i);
            }
        }

        return result;
    }

    private List<Integer> kmp_search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        if (m == 0 || n < m) {
            return new ArrayList<>();
        }

        int[] lps = new int[m];
        int length = 0;
        int i = 1;
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        List<Integer> indices = new ArrayList<>();
        i = 0;
        int j = 0;
        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }

            if (j == m) {
                indices.add(i - j);
                j = lps[j - 1];
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return indices;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 3008: Find Beautiful Indices in the Given Array II - Detailed explanation and solution approaches.

Topics

Two Pointers String Binary Search Rolling Hash String Matching Hash Function

Companies

Palantir TechnologiesPhonePe

Stats

Difficulty:Hard

Languages:4

Companies:2

Problem #:3008

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Implement KMP Search: Implement the KMP algorithm to find all starting indices where string `a` appears in string `s` and store these indices in a list called `indices_a`. Repeat the same process for string `b`, storing the indices in `indices_b`.
2
Step 2: Handle Empty Cases: If either `indices_a` or `indices_b` is empty, then no beautiful indices exist, and return an empty list.
3
Step 3: Iterate through 'a' indices and find valid 'b' indices: Iterate through each index `i` in `indices_a`. For each `i`, use a second pointer (`j_ptr`) to find an index `j` in `indices_b` such that `|i - j| <= k`.
4
Step 4: Two-Pointer Optimization for 'b' index search: Increment `j_ptr` until `indices_b[j_ptr]` is greater than or equal to `i - k`. If `j_ptr` reaches the end of `indices_b` or if `indices_b[j_ptr]` is greater than `i + k`, then there is no suitable `j` in `indices_b` for the current `i`.
5
Step 5: Check the 'k' distance constraint: If `j_ptr` is within the bounds of `indices_b` and `indices_b[j_ptr]` is less than or equal to `i + k`, then the 'k' distance condition is met, and `i` is a beautiful index. Add it to result.
6
Step 6: Return Result: After iterating through all indices in `indices_a`, return the sorted list of beautiful indices.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n*m + n*l + len(indices_a)*len(indices_b))

💾

Space Complexity

O(n + m + l)

📝

Why?

The complexity is dominated by the KMP searches (O(n+m), O(n+l)) and the search for matching 'b' indices for each 'a' index within the k distance. The LPS array creation in KMP contributes to the space complexity and takes O(m) or O(l) space

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute-Force

Iterate through all possible starting indices in 's'. For each index i, check if the substring starting at i matches 'a'. If it does, iterate through all possible starting indices j and check if the substring at j matches 'b'. Then, check if |i - j| <= k.

Time: O(n^3) - Two nested loops for indices i and j and another loop for checking if substring matchesSpace: O(1)

Trade-offs: Simpler to implement, but extremely inefficient for large inputs. Should be avoided.

Rolling Hash

Use a rolling hash function (e.g., Rabin-Karp) to quickly find potential matches of a and b within s. Then, verify the matches.

Time: O(n + m + l) on average, O(n*m) in worst case due to collisions.Space: O(1)

Trade-offs: Rolling hash offers good average performance, but can degrade to O(n*m) in the worst case due to hash collisions. KMP is usually preferred due to its guaranteed O(n+m) performance. But rolling hash requires less space than KMP.

✨

Key Insights

1Insight 1: Efficient String Matching: The core of the problem involves finding all occurrences of substrings `a` and `b` within `s`. A naive approach of comparing every possible substring would be inefficient, leading to a higher time complexity. Thus KMP Algorithm must be used.
2Insight 2: Two-Pointer Optimization: After identifying the indices of occurrences of `a` and `b`, the problem requires finding pairs of indices `i` and `j` within a specified distance `k`. A brute-force approach would be inefficient. The efficient approach uses the sorted indices of 'b' to quickly check the 'k' distance constraint.
3Insight 3: Handling Empty Result: Pay attention to the edge cases where no occurrences of `a` or `b` are found in `s`. In this situation, the function must return an empty list.

📚

Key Terms Explained

For Students

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string 's': If the input string `s` is empty, the KMP algorithm will return an empty list of indices for both `a` and `b`, resulting in an empty result, which is the correct behavior.
Edge case 2: Empty string 'a' or 'b': If string `a` or `b` are empty, the KMP algorithm will handle this gracefully. The main function will check for empty result after the kmp search.
Edge case 3: No occurrences of 'a' or 'b': If there are no occurrences of 'a' or 'b' in 's', the result will be empty which fulfills requirements.
Edge case 4: k = 0 : When k = 0, the index i for 'a' has to have exact same index j for 'b'.
Edge case 5: All occurrences of 'b' occur before or after indices of 'a'. The two pointer approach will skip all of these.
Edge case 6: Duplicates: The problem statement guarantees that results must be in sorted order from smallest to largest, and that there won't be duplicate occurrences of 'a' or 'b' indices for the same string 's', 'a', 'b', 'k'. This removes ambiguity of same indices appearing more than once in output.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling empty cases for `indices_a` and `indices_b`. This results in wrong results or errors.

✗Common mistake 2: Using inefficient substring comparison methods. This greatly increases the overall runtime complexity of the algorithm. KMP drastically reduces this.

✗Common mistake 3: Incorrectly implementing the 'k' distance check, leading to missing beautiful indices or including incorrect ones.

✗Common mistake 4: Not sorting the output array, resulting in an incorrect answer.

✗Common mistake 5: Integer overflow when calculating absolute difference |i - j|. Although constraints don't point to this as a high risk, it's generally good to be careful.

✗Common mistake 6: Memory leaks or incorrect pointer management in C.

✗Common mistake 7: Not correctly allocating memory for result arrays in C.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Bioinformatics - Identifying DNA sequences (analogous to strings a and b) within a larger genome (string s) and finding if these sequences are located close enough to each other within a certain region (k).

🏦Real-world scenario 2: Text Editors/Search Engines - Finding occurrences of a specific word or phrase (string a) near other keywords or phrases (string b) within a document or web page (string s). Useful for advanced search features.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The two-pointer technique is powerful for sorted arrays. The key insight is recognizing when elements can be processed from both ends simultaneously.

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

The most common mistake is not handling the case when pointers meet. Always consider the termination condition.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 7, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

❓

Frequently Asked Questions

When is the two-pointer technique most effective?

Two pointers work best on sorted arrays or when searching for pairs/triplets that satisfy a condition. Common patterns include: moving pointers inward from both ends (like in two-sum variants), fast/slow pointers for cycle detection, or left/right pointers for partitioning.

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Find Beautiful Indices in the Given Array II"?

For this hard-level Two Pointers problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?