Summer Trip
InterviewTime limit3sMemory limit1024 MB
Given a string of event types, count contiguous substrings of length at least two whose first and last characters are distinct and each appears only once in the substring.
- Level
Medium5 of 10
- Topics
- String, Two pointers, Prefix sum, Combinatorics
- Solved
- No attempts yet
Problem
Leo has started a job at a travel agency. His first task is to organize a summer trip to an exotic overseas city. During the summer season, events of various types take place in the city: sports matches, concerts, beach parties, and many others. At any given time, exactly one event is taking place. Events of any particular type may take place more than once during the season.
The itinerary of events that Leo offers to his clients cannot be chosen arbitrarily; the company requires that it form a so-called "good itinerary." A good itinerary is a consecutive sequence of at least two events in the summer season where the first and last events are of different types, and each of those two types is unique among all event types during the sequence. For example, if the first event in a good itinerary is a beach party, none of the other events during the itinerary can also be a beach party. There are no other restrictions on the event types in the sequence of a good itinerary.
Before he starts organizing the trip, Leo wants to know the total number of good itineraries that are possible given a calendar of events that will take place over the summer season.
Input
The input consists of one line with a string describing the sequence of event types in the summer season. All characters are lowercase English letters ('a' to 'z'), and different letters represent different types of events. Character i of the string encodes the ith event of the summer. There are no blanks or spaces in the string.
The length of the input string is at least 2 and at most 100 000 characters.
Output
Print the number of good itineraries that exist for the given summer season.