Algorithms
Medium
3006
3245
Find Beautiful Indices in the Given Array I
find-beautiful-indices-in-the-given-array-i
"""
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.
"""
class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        
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.


Please complete the code below to solve above prblem:
```python
class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        
```

my_solution = Solution()

test_input = { "s": "isawsquirrelnearmysquirrelhouseohmy", "a": "my", "b": "squirrel", "k": 15 }
assert my_solution.beautifulIndices(**test_input) == [16,33]

test_input = { "s": "abcd", "a": "a", "b": "a", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == [0]

test_input = { "s": "sqgrt", "a": "rt", "b": "sq", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == [3]

test_input = { "s": "mquz", "a": "tklr", "b": "caz", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "wl", "a": "xjigt", "b": "wl", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "bavgoc", "a": "ba", "b": "c", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == [0]

test_input = { "s": "xpcp", "a": "yxnod", "b": "xpc", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "lahhnlwx", "a": "hhnlw", "b": "ty", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "dexgscgecd", "a": "gscge", "b": "d", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == [3]

test_input = { "s": "vjrao", "a": "vjr", "b": "yxpsw", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "oo", "a": "swhup", "b": "o", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "bxlzgxc", "a": "ducf", "b": "xlzgx", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "wetlgztzm", "a": "box", "b": "wetl", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "ocmm", "a": "m", "b": "oc", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == [2,3]

test_input = { "s": "goxmox", "a": "gibs", "b": "ox", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "kzlrqzldvy", "a": "zl", "b": "tfsr", "k": 9 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "qhd", "a": "hd", "b": "od", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "bozpeh", "a": "bozp", "b": "vrjn", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "ggfsg", "a": "gfsg", "b": "g", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == [1]

test_input = { "s": "fape", "a": "vq", "b": "ap", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "isitbenom", "a": "pmng", "b": "itben", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "gw", "a": "ln", "b": "gw", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "jhu", "a": "sio", "b": "xnx", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "elcklvcvdg", "a": "lck", "b": "e", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == [1]

test_input = { "s": "subsu", "a": "tdo", "b": "su", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "jqcdc", "a": "c", "b": "d", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == [2,4]

test_input = { "s": "hhvc", "a": "gfwo", "b": "hh", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "tyoq", "a": "vhjit", "b": "yoq", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "rtbp", "a": "migjb", "b": "es", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "gkkstqvl", "a": "gkkst", "b": "xszl", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "bc", "a": "spzk", "b": "wsick", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "gyalx", "a": "neet", "b": "rbhl", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "qo", "a": "agt", "b": "xrh", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "rinzbrrr", "a": "nzb", "b": "r", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == [2]

test_input = { "s": "tjly", "a": "j", "b": "n", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "frkxslnnn", "a": "rkxsl", "b": "n", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "cffczbccc", "a": "ff", "b": "c", "k": 9 }
assert my_solution.beautifulIndices(**test_input) == [1]

test_input = { "s": "uiddqbeoaw", "a": "iddq", "b": "rlr", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "fh", "a": "ywab", "b": "qcjyl", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "gdbm", "a": "gdbm", "b": "uefwm", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "bpcwswu", "a": "zi", "b": "pcwsw", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "dh", "a": "jmcds", "b": "nytk", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "qjgckhiif", "a": "hiif", "b": "jgc", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == [5]

test_input = { "s": "qyixufgyk", "a": "y", "b": "ixuf", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == [1,7]

test_input = { "s": "wiwiwinwio", "a": "hm", "b": "wi", "k": 8 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "ffnlge", "a": "bjt", "b": "pavkr", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "rj", "a": "m", "b": "umg", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "bkgqxl", "a": "yufy", "b": "kgq", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "hhcwp", "a": "sixek", "b": "cwp", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "czr", "a": "cz", "b": "wxxql", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "tdbnme", "a": "t", "b": "dbnme", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == [0]

test_input = { "s": "px", "a": "acgz", "b": "jaxel", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "wfa", "a": "fyntx", "b": "a", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "ixfkxfld", "a": "ixfk", "b": "urkke", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "kmjvlkjy", "a": "gll", "b": "vlk", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "bsbsvnmvnm", "a": "vnm", "b": "bs", "k": 7 }
assert my_solution.beautifulIndices(**test_input) == [4,7]

test_input = { "s": "uzqauzqw", "a": "uzq", "b": "psnso", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "fsvkche", "a": "yot", "b": "svkc", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "cwwzmfzz", "a": "fnlgc", "b": "cwwzm", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "profguo", "a": "o", "b": "oyzje", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "ckbdnw", "a": "djpc", "b": "ckbdn", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "ankfahcorr", "a": "r", "b": "kfah", "k": 7 }
assert my_solution.beautifulIndices(**test_input) == [8,9]

test_input = { "s": "ahjzfg", "a": "hjzf", "b": "zs", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "eueuau", "a": "u", "b": "e", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == [1,3,5]

test_input = { "s": "etuwwhwljf", "a": "uwwh", "b": "efcuq", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "vvjhgg", "a": "g", "b": "kj", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "igytmsmsgx", "a": "msmsg", "b": "gyt", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == [4]

test_input = { "s": "cheoeo", "a": "eo", "b": "y", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "gqzf", "a": "cgpdn", "b": "zf", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "zapqwtmx", "a": "apqwt", "b": "m", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "klxtee", "a": "e", "b": "klx", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "xa", "a": "gzsj", "b": "oooq", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "gxoxqgxoxq", "a": "gxoxq", "b": "x", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == [0,5]

test_input = { "s": "lsuo", "a": "d", "b": "uo", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "yhi", "a": "ph", "b": "yhi", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "cj", "a": "j", "b": "em", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "clxzclxz", "a": "ge", "b": "clxz", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "gjtcpyiniv", "a": "cpyi", "b": "hjvtq", "k": 9 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "kyrvedszzo", "a": "rve", "b": "y", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == [2]

test_input = { "s": "makolbcrme", "a": "qlhpf", "b": "akol", "k": 9 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "vgxshd", "a": "vgx", "b": "en", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "wfvxfzut", "a": "wfv", "b": "ut", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == [0]

test_input = { "s": "xxtxxuftxt", "a": "tx", "b": "x", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == [2,7]

test_input = { "s": "cwtybs", "a": "wgfez", "b": "cwty", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "opnkctux", "a": "op", "b": "nkctu", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == [0]

test_input = { "s": "swswmcsksw", "a": "mcsk", "b": "sw", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == [4]

test_input = { "s": "qqnb", "a": "q", "b": "q", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == [0,1]

test_input = { "s": "tt", "a": "t", "b": "q", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "lllclbii", "a": "l", "b": "i", "k": 7 }
assert my_solution.beautifulIndices(**test_input) == [0,1,2,4]

test_input = { "s": "oanyzue", "a": "yzu", "b": "oan", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == [3]

test_input = { "s": "opmfgzthj", "a": "opmf", "b": "g", "k": 9 }
assert my_solution.beautifulIndices(**test_input) == [0]

test_input = { "s": "uiddidde", "a": "idd", "b": "sal", "k": 7 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "gzzau", "a": "za", "b": "rwu", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "srpxqurxx", "a": "nsr", "b": "x", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "sxaono", "a": "jy", "b": "xaon", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "acxtjiova", "a": "acx", "b": "tjiov", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == [0]

test_input = { "s": "iltazkww", "a": "k", "b": "z", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == [5]

test_input = { "s": "ltxbhpi", "a": "cjfbb", "b": "ltxb", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "gysgysh", "a": "gys", "b": "qzvae", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "zypvgt", "a": "zypv", "b": "ljxni", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == []