Scale Engineer

Find Beautiful Indices in the Given Array I

Med
#2674Time: O(N*M + P*Q), where N is `s.length()`, M is `max(a.length(), b.length())`, P is the count of `a`'s occurrences, and Q is the count of `b`'s occurrences. In the worst case, P and Q can be O(N), making the complexity O(N^2).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
Palantir TechnologiesSamsara

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 <= 105
  • 1 <= a.length, b.length <= 10
  • s, a, and b contain only lowercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach is a straightforward, brute-force solution. It first identifies all occurrences of the substrings a and b within the main string s and stores their starting indices in two separate lists. Afterwards, it employs a pair of nested loops to compare every index from the first list against every index from the second. If any pair of indices (i, j) satisfies the condition |i - j| <= k, the index i is marked as beautiful and added to the result.

Algorithm

  • Create two lists, indicesA and indicesB, to store the starting indices of all occurrences of strings a and b in s.
  • Populate indicesA by iterating through s and checking for a at each position.
  • Populate indicesB similarly by checking for b.
  • Initialize an empty list result to store the beautiful indices.
  • Iterate through each index i in indicesA with an outer loop.
  • Inside, use a nested loop to iterate through each index j in indicesB.
  • If Math.abs(i - j) <= k, it means i is a beautiful index. Add i to result and break the inner loop to proceed to the next i.
  • Return the result list.

Walkthrough

The implementation involves two main steps. First, we scan the string s twice to find all starting positions for a and b. A simple way to do this is by iterating from 0 to s.length() - pattern.length() and using s.startsWith(pattern, i). The found indices are stored in indicesA and indicesB.

Second, we iterate through each index i in indicesA. For each i, we iterate through all indices j in indicesB. We calculate the absolute difference |i - j| and check if it's less than or equal to k. If the condition holds, we add i to our result list and use break to stop searching for other j's for the current i, as one is sufficient.

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<>();        for (int i = 0; i <= n - lenA; i++) {            if (s.startsWith(a, i)) {                indicesA.add(i);            }        }         List<Integer> indicesB = new ArrayList<>();        for (int i = 0; i <= n - lenB; i++) {            if (s.startsWith(b, i)) {                indicesB.add(i);            }        }         List<Integer> result = new ArrayList<>();        if (indicesA.isEmpty() || indicesB.isEmpty()) {            return result;        }         for (int i : indicesA) {            for (int j : indicesB) {                if (Math.abs(i - j) <= k) {                    result.add(i);                    break; // Found a valid j, move to the next i                }            }        }        return result;    }}

Complexity

Time

O(N*M + P*Q), where N is `s.length()`, M is `max(a.length(), b.length())`, P is the count of `a`'s occurrences, and Q is the count of `b`'s occurrences. In the worst case, P and Q can be O(N), making the complexity O(N^2).

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

  • Easy to understand and implement.

  • Works correctly for small inputs.

Cons

  • The nested loop for checking the distance condition leads to a quadratic time complexity in the worst case, which is highly inefficient for large inputs.

  • It is likely to result in a 'Time Limit Exceeded' error on platforms with strict time constraints.

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