Algorithms
Hard
3008
3303
Find Beautiful Indices in the Given Array II
find-beautiful-indices-in-the-given-array-ii
"""
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.
"""
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 <= 5 * 105
1 <= a.length, b.length <= 5 * 105
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": "a", "a": "a", "b": "a", "k": 1 }
assert my_solution.beautifulIndices(**test_input) == [0]

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

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

test_input = { "s": "npearbvede", "a": "myqpb", "b": "pearb", "k": 9 }
assert my_solution.beautifulIndices(**test_input) == []

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

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

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

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

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

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

test_input = { "s": "wltmqbxt", "a": "mqbxt", "b": "lt", "k": 7 }
assert my_solution.beautifulIndices(**test_input) == [3]

test_input = { "s": "gggsytwgzg", "a": "sytwg", "b": "g", "k": 4 }
assert my_solution.beautifulIndices(**test_input) == [3]

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

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

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

test_input = { "s": "xllimtmil", "a": "imt", "b": "iwqx", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

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

test_input = { "s": "ouwpaz", "a": "mxre", "b": "pa", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

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

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

test_input = { "s": "owhixi", "a": "hixi", "b": "anlc", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == []

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

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

test_input = { "s": "imxclscgz", "a": "iujc", "b": "mxcls", "k": 7 }
assert my_solution.beautifulIndices(**test_input) == []

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

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

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

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

test_input = { "s": "youob", "a": "y", "b": "o", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == [0]

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

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

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

test_input = { "s": "avnzbrpb", "a": "yzfgy", "b": "cfri", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

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

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

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

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

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

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

test_input = { "s": "onwawarwa", "a": "wa", "b": "r", "k": 2 }
assert my_solution.beautifulIndices(**test_input) == [4,7]

test_input = { "s": "xpuldtpxpu", "a": "vkhl", "b": "xpu", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

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

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

test_input = { "s": "gfjuakm", "a": "fj", "b": "jytnd", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

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

test_input = { "s": "zwedfgnra", "a": "dfgn", "b": "zwe", "k": 9 }
assert my_solution.beautifulIndices(**test_input) == [3]

test_input = { "s": "nipetnupg", "a": "n", "b": "ipet", "k": 7 }
assert my_solution.beautifulIndices(**test_input) == [0,5]

test_input = { "s": "xckrhkrnfe", "a": "xc", "b": "kr", "k": 9 }
assert my_solution.beautifulIndices(**test_input) == [0]

test_input = { "s": "xibrjp", "a": "ibr", "b": "bpfuf", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == []

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

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

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

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

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

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

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

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

test_input = { "s": "yalimlim", "a": "lim", "b": "bwi", "k": 8 }
assert my_solution.beautifulIndices(**test_input) == []

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

test_input = { "s": "dyswswiz", "a": "tib", "b": "dysws", "k": 7 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "ftyhkld", "a": "tyh", "b": "znru", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "adubkehe", "a": "kdtxl", "b": "dubke", "k": 7 }
assert my_solution.beautifulIndices(**test_input) == []

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

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

test_input = { "s": "arikarikox", "a": "o", "b": "arik", "k": 8 }
assert my_solution.beautifulIndices(**test_input) == [8]

test_input = { "s": "cigzky", "a": "cigz", "b": "tu", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "hjlllm", "a": "l", "b": "h", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == [2,3,4]

test_input = { "s": "xiyebjzdbv", "a": "iqku", "b": "yebjz", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

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

test_input = { "s": "lagopphhnl", "a": "gopph", "b": "hnl", "k": 8 }
assert my_solution.beautifulIndices(**test_input) == [2]

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

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

test_input = { "s": "swuaumom", "a": "swuau", "b": "m", "k": 8 }
assert my_solution.beautifulIndices(**test_input) == [0]

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

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

test_input = { "s": "egzttzmtot", "a": "boxwe", "b": "t", "k": 9 }
assert my_solution.beautifulIndices(**test_input) == []

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

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

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

test_input = { "s": "qkddvykd", "a": "kd", "b": "tprs", "k": 8 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "vndnqdehvr", "a": "dnqd", "b": "ybboz", "k": 8 }
assert my_solution.beautifulIndices(**test_input) == []

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

test_input = { "s": "lgioimioim", "a": "imsfs", "b": "ioim", "k": 10 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "jhucel", "a": "iox", "b": "nx", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

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

test_input = { "s": "buyryryrjq", "a": "yr", "b": "u", "k": 9 }
assert my_solution.beautifulIndices(**test_input) == [2,4,6]

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

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

test_input = { "s": "tssjrbpsck", "a": "ssjr", "b": "sc", "k": 10 }
assert my_solution.beautifulIndices(**test_input) == [1]

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

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

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

test_input = { "s": "angkytf", "a": "ngk", "b": "ytf", "k": 7 }
assert my_solution.beautifulIndices(**test_input) == [1]

test_input = { "s": "oloxjjjqj", "a": "olox", "b": "j", "k": 7 }
assert my_solution.beautifulIndices(**test_input) == [0]

test_input = { "s": "zbriomnn", "a": "omn", "b": "zbr", "k": 6 }
assert my_solution.beautifulIndices(**test_input) == [4]

test_input = { "s": "ydmlx", "a": "tu", "b": "dml", "k": 5 }
assert my_solution.beautifulIndices(**test_input) == []

test_input = { "s": "lnoffflno", "a": "lno", "b": "f", "k": 3 }
assert my_solution.beautifulIndices(**test_input) == [0,6]

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