Welcome to Subscribe On Youtube

3006. Find Beautiful Indices in the Given Array I

Description

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.

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;
        }
    }
    
    
  • class Solution {
    public:
        vector<int> beautifulIndices(string s, string patternA, string patternB, int k) {
            vector<int> beautifulIndicesA = kmpSearch(s, patternA);
            vector<int> beautifulIndicesB = kmpSearch(s, patternB);
    
            sort(beautifulIndicesB.begin(), beautifulIndicesB.end());
    
            vector<int> result;
            for (int indexA : beautifulIndicesA) {
                int left = lower_bound(beautifulIndicesB.begin(), beautifulIndicesB.end(), indexA - k) - beautifulIndicesB.begin();
                int right = lower_bound(beautifulIndicesB.begin(), beautifulIndicesB.end(), indexA + k + patternB.length()) - beautifulIndicesB.begin();
    
                left = (left >= 0) ? left : -(left + 1);
                right = (right >= 0) ? right : -(right + 1);
    
                for (int indexB = left; indexB < right; indexB++) {
                    if (abs(beautifulIndicesB[indexB] - indexA) <= k) {
                        result.push_back(indexA);
                        break;
                    }
                }
            }
    
            return result;
        }
    
    private:
        vector<int> kmpSearch(string text, string pattern) {
            vector<int> indices;
            vector<int> pi = computePrefixFunction(pattern);
    
            int q = 0;
            for (int i = 0; i < text.length(); i++) {
                while (q > 0 && pattern[q] != text[i]) {
                    q = pi[q - 1];
                }
                if (pattern[q] == text[i]) {
                    q++;
                }
                if (q == pattern.length()) {
                    indices.push_back(i - q + 1);
                    q = pi[q - 1];
                }
            }
    
            return indices;
        }
    
        vector<int> computePrefixFunction(string pattern) {
            int m = pattern.length();
            vector<int> pi(m, 0);
            int k = 0;
            for (int q = 1; q < m; q++) {
                while (k > 0 && pattern[k] != pattern[q]) {
                    k = pi[k - 1];
                }
                if (pattern[k] == pattern[q]) {
                    k++;
                }
                pi[q] = k;
            }
            return pi;
        }
    };
    
    
  • class Solution:
        def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
            def build_prefix_function(pattern):
                prefix_function = [0] * len(pattern)
                j = 0
                for i in range(1, len(pattern)):
                    while j > 0 and pattern[i] != pattern[j]:
                        j = prefix_function[j - 1]
                    if pattern[i] == pattern[j]:
                        j += 1
                    prefix_function[i] = j
                return prefix_function
    
            def kmp_search(pattern, text, prefix_function):
                occurrences = []
                j = 0
                for i in range(len(text)):
                    while j > 0 and text[i] != pattern[j]:
                        j = prefix_function[j - 1]
                    if text[i] == pattern[j]:
                        j += 1
                    if j == len(pattern):
                        occurrences.append(i - j + 1)
                        j = prefix_function[j - 1]
                return occurrences
    
            prefix_a = build_prefix_function(a)
            prefix_b = build_prefix_function(b)
    
            resa = kmp_search(a, s, prefix_a)
            resb = kmp_search(b, s, prefix_b)
    
            res = []
            print(resa, resb)
            i = 0
            j = 0
            while i < len(resa):
                while j < len(resb):
                    if abs(resb[j] - resa[i]) <= k:
                        res.append(resa[i])
                        break
                    elif j + 1 < len(resb) and abs(resb[j + 1] - resa[i]) < abs(
                        resb[j] - resa[i]
                    ):
                        j += 1
                    else:
                        break
                i += 1
            return res
    
    
  • func beautifulIndices(s string, a string, b string, k int) []int {
    
    	s_len := len(s)
    	a_len := len(a)
    	b_len := len(b)
    
    	final := make([]int, 0)
    	lps_a := make([]int, a_len)
    	lps_b := make([]int, b_len)
    	a_index := make([]int, 0)
    	b_index := make([]int, 0)
    
    	var pat func(lps []int, s_l int, pattern string)
    
    	pat = func(lps []int, s_l int, pattern string) {
    
    		l := 0
    		lps[0] = 0
    		i := 1
    
    		for i < s_l {
    			if pattern[i] == pattern[l] {
    				l++
    				lps[i] = l
    				i++
    			} else {
    				if l != 0 {
    					l = lps[l-1]
    				} else {
    					lps[i] = l
    					i++
    				}
    			}
    		}
    	}
    
    	pat(lps_a, a_len, a)
    	pat(lps_b, b_len, b)
    
    	var kmp func(pat string, pat_l int, lps []int, index *[]int)
    
    	kmp = func(pat string, pat_l int, lps []int, index *[]int) {
    		i := 0
    		j := 0
    		for s_len-i >= pat_l-j {
    			if s[i] == pat[j] {
    				i++
    				j++
    			}
    			if j == pat_l {
    				*index = append(*index, i-pat_l)
    				j = lps[j-1]
    			} else if s[i] != pat[j] {
    				if j != 0 {
    					j = lps[j-1]
    				} else {
    					i++
    				}
    			}
    		}
    	}
    
    	kmp(a, a_len, lps_a, &a_index)
    	kmp(b, b_len, lps_b, &b_index)
    
    	// fmt.Println(a_index, b_index)
    
    	i := 0
    	j := 0
    
    	for i < len(a_index) && j < len(b_index) {
    		if a_index[i]+k >= b_index[j] && a_index[i]-k <= b_index[j] {
    			final = append(final, a_index[i])
    			i++
    		} else if a_index[i]-k > b_index[j] {
    			j++
    		} else {
    			i++
    		}
    	}
    
    	return final
    }
    
    

All Problems

All Solutions