Strong Password (Codeforces 1845C)
Tags: Greedy, strings

Monocarp finally got the courage to register on ForceCoders. He came up with a handle but is still thinking about the password.He wants his password to be as strong as possible, so he came up with the following criteria:   the length of the password should be exactly $$$m$$$;  the password should only consist of digits from $$$0$$$ to $$$9$$$;  the password should not appear in the password database (given as a string $$$s$$$) as a subsequence (not necessarily contiguous). Monocarp also came up with two strings of length $$$m$$$: $$$l$$$ and $$$r$$$, both consisting only of digits from $$$0$$$ to $$$9$$$. He wants the $$$i$$$-th digit of his password to be between $$$l_i$$$ and $$$r_i$$$, inclusive.Does there exist a password that fits all criteria?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.The first line of each testcase contains a string $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$), consisting only of digits from $$$0$$$ to $$$9$$$ — the password database.The second line contains a single integer $$$m$$$ ($$$1 \le m \le 10$$$) — the required length of the password.The third line contains a string $$$l$$$ ($$$|l| = m$$$), consisting only of digits from $$$0$$$ to $$$9$$$ — the lower restriction on each digit.The fourth line contains a string $$$r$$$ ($$$|r| = m$$$), consisting only of digits from $$$0$$$ to $$$9$$$ — the upper restriction on each digit. $$$l_i \le r_i$$$ for all $$$i$$$ from $$$1$$$ to $$$m$$$.The sum of lengths of $$$s$$$ over all testcases doesn't exceed $$$3 \cdot 10^5$$$.

Output: For each testcase, print "YES" if there exists a password that fits all criteria. Print "NO" otherwise.

Note: In the first testcase, Monocarp can choose password "50". It doesn't appear in $$$s$$$ as a subsequence.In the second testcase, all combinations of three digits, each of them being from $$$1$$$ to $$$4$$$, fit the criteria on $$$l$$$ and $$$r$$$. However, all of them appear in $$$s$$$ as subsequences. For example, "314" appears at positions $$$[3, 5, 12]$$$ and "222" appears at positions $$$[2, 6, 10]$$$.In the third testcase, Monocarp can choose password "4321". Actually, that is the only password that fits the criteria on $$$l$$$ and $$$r$$$. Luckily, it doesn't appear in $$$s$$$ as a subsequence.In the fourth testcase, only "49" and "59" fit the criteria on $$$l$$$ and $$$r$$$. Both of them appear in $$$s$$$ as subsequences.In the fifth testcase, Monocarp can choose password "11".

Sample Inputs:
5
88005553535123456
2
50
56
123412341234
3
111
444
1234
4
4321
4321
459
2
49
59
00010
2
10
11

Sample Outputs:
YES
NO
YES
NO
YES

Solution (Python):
from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

def ni():
    return int(input())

def si():
    return input()

def mi():
    return map(int, input().strip().split())

def li():
    return list(map(int, input().strip().split()))

def main():
    for _ in range(ni()):
        s = si()
        m = ni()
        l = si()
        r = si()
        ind = 0
        doable = 'NO'
        for i in range(m):
            ind = 0
            for j in range(int(l[i]), int(r[i]) + 1):
                try:
                    a = s.index(str(j))
                    if a > ind:
                        ind = a
                except:
                    doable = 'YES'
                if doable == 'YES':
                    break
            if doable == 'YES':
                break
            s = s[ind + 1:]
        print(doable)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

def ni():
    return int(input())

def si():
    return input()

def mi():
    return map(int, input().strip().split())

def li():
    return list(map(int, input().strip().split()))

def main():
    global perms, mains
    for _ in range(ni()):
        s = si()
        m = ni()
        l = si()
        r = si()
        ind = 0
        doable = 'NO'
        for i in range(m):
            ind = 0
            for j in range(int(l[i]), int(r[i]) + 1):
                try:
                    a = s.index(str(j))
                    if a > ind:
                        ind = a
                except:
                    doable = 'YES'
                if doable == 'YES':
                    break
            if doable == 'YES':
                break
            if s == '':
                doable == 'YES'
                break
            s = s[ind + 1:]
        print(doable)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
def find_character_from_index(string, c1, c2, start_index):
    substring = string[start_index:]
    c = c1
    mx = start_index
    while c <= c2:
        try:
            position = substring.index(c)
            mx = max(mx, position + start_index)
        except ValueError:
            return -1
        c = ord(c)
        c = chr(c + 1)
    return mx
if __name__ == '__main__':
    test_case = int(input())
    for tc in range(test_case):
        db = input()
        n = int(input())
        a = input()
        b = input()
        possible = False
        current_pos = 0
        for i in range(n):
            current_pos = find_character_from_index(db, a[i], b[i], current_pos)
            if current_pos == -1:
                possible = True
                break
            else:
                current_pos += 1
        print('Yes') if possible else print('No')