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.lengths[i..(i + a.length - 1)] == a- There exists an index
jsuch that:0 <= j <= s.length - b.lengths[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 <= 1051 <= a.length, b.length <= 10s,a, andbcontain 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 }