Scale Engineer

Find Beautiful Indices in the Given Array II

Hard
#2676Time: O(N*M_a + N*M_b + P*Q), where N is `s.length()`, M_a is `a.length()`, M_b is `b.length()`, P is `|indicesA|`, and Q is `|indicesB|`. In the worst case, this can be O(N^2), which is very inefficient.Space: O(P + Q), where P and Q are the number of occurrences of `a` and `b` respectively. In the worst case, this can be O(N), where N is the length of `s`.2 companies
Patterns
Two PointersString MatchingRolling HashHash Function
Algorithms
Binary Search
Data structures
String
Companies
PhonePePalantir Technologies

Prompt

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 are 2 beautiful indices: [16,33].
- The index 16 is beautiful as s[16..17] == "my" and there exists an index 4 with s[4..11] == "squirrel" and |16 - 4| <= 15.
- The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 - 18| <= 15.
Thus we return [16,33] as the result.

Example 2:

Input: s = "abcd", a = "a", b = "a", k = 4
Output: [0]
Explanation: There is 1 beautiful index: [0].
- The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 - 0| <= 4.
Thus we return [0] as the result.

 

Constraints:

  • 1 <= k <= s.length <= 5 * 105
  • 1 <= a.length, b.length <= 5 * 105
  • s, a, and b contain only lowercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach is a direct, straightforward implementation based on the problem description. It first finds all starting indices of substrings a and b in s using a naive string matching method. Then, for every occurrence of a at index i, it performs a linear scan through all occurrences of b at index j to check if the distance condition |i - j| <= k is satisfied.

Algorithm

  • Initialize two empty lists, indicesA and indicesB.
  • Find all occurrences of string a in s:
    • Iterate from i = 0 to s.length - a.length.
    • If s.substring(i, i + a.length) equals a, add i to indicesA.
  • Find all occurrences of string b in s:
    • Iterate from j = 0 to s.length - b.length.
    • If s.substring(j, j + b.length) equals b, add j to indicesB.
  • Initialize an empty list result.
  • For each index i in indicesA:
    • For each index j in indicesB:
      • If |i - j| <= k, add i to result and break the inner loop to check the next i.
  • Return result.

Walkthrough

The method involves three main steps. First, we create a list indicesA by iterating through the string s and checking for a at every possible starting position using substring comparisons. Second, we do the same for string b to populate a list indicesB. Finally, we use nested loops to iterate through indicesA and indicesB. For each pair of indices (i, j), we check if their absolute difference is at most k. If the condition holds, we add i to our result list and move to the next index in indicesA to avoid duplicates.

import java.util.ArrayList;import java.util.List; class Solution {    public List<Integer> beautifulIndices(String s, String a, String b, int k) {        int n = s.length();        int lenA = a.length();        int lenB = b.length();        List<Integer> indicesA = new ArrayList<>();        List<Integer> indicesB = new ArrayList<>();         for (int i = 0; i <= n - lenA; i++) {            if (s.substring(i, i + lenA).equals(a)) {                indicesA.add(i);            }        }         for (int i = 0; i <= n - lenB; i++) {            if (s.substring(i, i + lenB).equals(b)) {                indicesB.add(i);            }        }         List<Integer> result = new ArrayList<>();        for (int i : indicesA) {            for (int j : indicesB) {                if (Math.abs(i - j) <= k) {                    result.add(i);                    break;                }            }        }        return result;    }}

Complexity

Time

O(N*M_a + N*M_b + P*Q), where N is `s.length()`, M_a is `a.length()`, M_b is `b.length()`, P is `|indicesA|`, and Q is `|indicesB|`. In the worst case, this can be O(N^2), which is very inefficient.

Space

O(P + Q), where P and Q are the number of occurrences of `a` and `b` respectively. In the worst case, this can be O(N), where N is the length of `s`.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Extremely slow due to nested loops and inefficient string searching.

  • Will cause a 'Time Limit Exceeded' (TLE) error on platforms with large test cases.

Solutions

public class Solution { public void computeLPS ( String pattern , int [] lps ) { int M = pattern . length (); int len = 0 ; lps [ 0 ] = 0 ; int i = 1 ; while ( i < M ) { if ( pattern . charAt ( i ) == pattern . charAt ( len )) { len ++; lps [ i ] = len ; i ++; } else { if ( len != 0 ) { len = lps [ len - 1 ]; } else { lps [ i ] = 0 ; i ++; } } } } public List < Integer > KMP_codestorywithMIK ( String pat , String txt ) { int N = txt . length (); int M = pat . length (); List < Integer > result = new ArrayList <>(); int [] lps = new int [ M ]; computeLPS ( pat , lps ); int i = 0 ; // Index for text int j = 0 ; // Index for pattern while ( i < N ) { if ( pat . charAt ( j ) == txt . charAt ( i )) { i ++; j ++; } if ( j == M ) { result . add ( i - j ); // Pattern found at index i-j+1 (If you have to return 1 Based // indexing, that's why added + 1) j = lps [ j - 1 ]; } else if ( i < N && pat . charAt ( j ) != txt . charAt ( i )) { if ( j != 0 ) { j = lps [ j - 1 ]; } else { i ++; } } } return result ; } private int lowerBound ( List < Integer > list , int target ) { int left = 0 , right = list . size () - 1 , result = list . size (); while ( left <= right ) { int mid = left + ( right - left ) / 2 ; if ( list . get ( mid ) >= target ) { result = mid ; right = mid - 1 ; } else { left = mid + 1 ; } } return result ; } public List < Integer > beautifulIndices ( String s , String a , String b , int k ) { int n = s . length (); List < Integer > i_indices = KMP_codestorywithMIK ( a , s ); List < Integer > j_indices = KMP_codestorywithMIK ( b , s ); List < Integer > result = new ArrayList <>(); for ( int i : i_indices ) { int left_limit = Math . max ( 0 , i - k ); // To avoid out of bound -> I used max(0, i-k) int right_limit = Math . min ( n - 1 , i + k ); // To avoid out of bound -> I used min(n-1, i+k) int lowerBoundIndex = lowerBound ( j_indices , left_limit ); if ( lowerBoundIndex < j_indices . size () && j_indices . get ( lowerBoundIndex ) <= right_limit ) { result . add ( i ); } } return result ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem