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

Xem PDF
Tác giả:
nhphucqt
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, bccaba và ccabab.

Bình luận


  • 0
    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, bccaba và ccabab.