Source code for titan_pylib.string.string_count

 1from titan_pylib.data_structures.fenwick_tree.fenwick_tree import FenwickTree
 2import string
 3
 4

[docs]
 5class StringCount:
 6
 7    def __init__(self, s: str, is_lower: bool = True):
 8        assert isinstance(s, str)
 9        self.alp: str = string.ascii_lowercase if is_lower else string.ascii_uppercase
10        self.DIC: dict[str, int] = {c: i for i, c in enumerate(self.alp)}
11        self.n: int = len(s)
12        self.s: list[str] = list(s)
13        dat: list[list[int]] = [[0] * self.n for _ in range(26)]
14        for i, c in enumerate(s):
15            dat[self.DIC[c]][i] += 1
16        self.data: list[FenwickTree] = [FenwickTree(d) for d in dat]
17

[docs]
18    def is_ascending(self, l: int, r: int) -> bool:
19        """区間[l, r)が昇順かどうか判定する / O(σlogn)"""
20        assert 0 <= l <= r <= self.n
21        end = l
22        for dat in self.data:
23            c = dat.sum(l, r)
24            end += c
25            if end > r or dat.sum(l, end) != c:
26                return False
27        return True

28

[docs]
29    def is_descending(self, l: int, r: int) -> bool:
30        """
31        区間[l, r)が降順かどうか判定する / O(σlogn)
32        Note: 未確認
33        """
34        assert 0 <= l <= r <= self.n
35        start = r - 1
36        for dat in reversed(self.data):
37            c = dat.sum(l, r)
38            start -= c
39            if start < l or dat.sum(start, r) != c:
40                return False
41        return True

42

[docs]
43    def get_min(self, l: int, r: int) -> str:
44        """区間[l, r)の最小の文字を返す / O(σlogn)"""
45        for i in range(26):
46            if self.data[i].sum(l, r):
47                return self.alp[i]
48        assert False, "Indexerror"

49

[docs]
50    def get_max(self, l: int, r: int) -> str:
51        """区間[l, r)の最大の文字を返す / O(σlogn)"""
52        for i in range(25, -1, -1):
53            if self.data[i].sum(l, r):
54                return self.alp[i]
55        assert False, "Indexerror"

56

[docs]
57    def __setitem__(self, k: int, c: str):
58        """k番目の文字をcに変更する / O(logn)"""
59        assert 0 <= k < self.n
60        self.data[self.DIC[self.s[k]]].add(k, -1)
61        self.s[k] = c
62        self.data[self.DIC[c]].add(k, 1)

63
64    # 区間[l, r)の全ての文字の個数を返す
65    # 返り値は要素数26のlist[int]

[docs]
66    def get_all_count(self, l: int, r: int) -> list[int]:
67        return [self.data[i].sum(l, r) for i in range(26)]

68

[docs]
69    def get_count(self, l: int, r: int, c: str) -> int:
70        """区間[l, r)のcの個数を返す / O(logn)"""
71        return self.data[self.DIC[c]].sum(l, r)

72
73    def __getitem__(self, k: int) -> str:
74        return self.s[k]
75
76    def __str__(self):
77        return "".join(self.s)