oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

reversecompare Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

reversecompare.html

Problem Statement

You have a string A = A_1 A_2 ... A_n consisting of lowercase English letters.

You can choose any two indices i and j such that 1 ≤ i ≤ j ≤ n and reverse substring A_i A_{i+1} ... A_j.

You can perform this operation at most once.

How many different strings can you obtain?

Input

Input is given from Standard Input in the following format:

A

Output

Print the number of different strings you can obtain by reversing any substring in A at most once.

Limits

For all subtasks: 1 ≤ |A| ≤ 200,000. A consists of lowercase English letters.

Subtask 1 (11%): 1 ≤ |A| ≤ 100

Subtask 2 (48%): 1 ≤ |A| ≤ 2000

Subtask 3 (41%): No additional contraints

Subtask 4 (0%): Sample Testcases

Sample Input 1

aatt

Sample Output 1

5

You can obtain aatt (don't do anything), atat (reverse A[2..3]), atta (reverse A[2..4]), ttaa (reverse A[1..4]) and taat (reverse A[1..3]).

Sample Input 2

xxxxxxxxxx

Sample Output 2

1

Whatever substring you reverse, you'll always get xxxxxxxxxx.

Sample Input 3

abracadabra

Sample Output 3

44

Tags

Ad Hoc

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
11151s256MBMinimum
24851s256MBMinimum
34151s256MBMinimum
4031s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o reversecompare -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.