CSES - Special Substrings | Xâu con đặc biệt

Xem PDF



Tác giả:
Dạng bài
Điểm: 1900 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một xâu con được gọi là đặc biệt nếu tất cả kí tự xuất hiện trong xâu gốc đều xuất hiện trong xâu con với số lần là bằng nhau.

Nhiệm vụ của bạn là đếm số lượng xâu con đặc biệt của xâu đã cho.

Input

  • Dòng đầu vào duy nhất có một xâu độ dài \(n\). Tất cả các kí tự nằm giữa a\(\dots\)z.

Output

  • In một số nguyên: số lượng xâu con đặc biệt.

Constraints

  • \(1 \le n \le 2 \cdot 10^5\)

Example

Sample input

abccabab

Sample output

5

Note

Các xâu con đặc biệt là: abc, cab, abccab, bccabaccabab.


Bình luận


  • -1
    nguyen_ducminh    11:32 p.m. 1 Tháng 9, 2023

    CSES - Special Substrings | Xâu con đặc biệt

    Một xâu con được gọi là đặc biệt nếu mọi kí tự xuất hiện trong xâu ban đầu đều xuất hiện trong xâu con đó với số lần bằng nhau.

    Nhiệm vụ của bạn là đếm số xâu con đặc biệt của một xâu cho trước.

    Input

    • Một xâu độ dài \(n\) (\(1 \leq n \leq 2\times10^5\)) gồm các kí tự a...z

    Output

    • Gồm một số nguyên là số xâu đặc biệt.

    Test 1

    Input
    abccabab
    Output
    5
    Note

    Các xâu con đặc biệt là abc, cab, abccab, bccabaccabab.