Unique Letter String

Image placeholder 9899Image placeholder 9899

(This question has been seen in the interviews of the following companies: Google, Amazon)

Unique Letter String

A character is unique in string S if it occurs exactly once in it. For example, in string S = "LETTER", the only unique characters are "L" and "R". Let's define UNIQ(S) as the number of unique characters in string S. For example, UNIQ("LETTER") =  2. Given a string S with only uppercases, calculate the sum of UNIQ(substring) over all non-empty substrings of S. If there are two or more equal substrings at different positions in S, we consider them different. Since the answer can be very large, retrun the answer modulo 10 ^ 9 7.

Example 1:

by interviewer and a shadow
Input: "ABC"
Output: 10
Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".
Every substring is composed with only unique letters.
Sum of lengths of all substring is 1 1 1 2 2 3 = 10

Example 2:

Input: "ABA"
Output: 8

    public int uniqueLetterString(String s) {
        int result = 0;
        for(char c = 'A';c <= 'Z'; c++){
            int tail = 0;
            int head = -1;
            int count = 0;
            for(int i=0;i < s.length();i++){
                if(s.charAt(i) == c){                
                    head = i;
                    count++;
                }
                while(count == 2){
                    if(s.charAt(tail++) == c){
                        count--;                        
                    }
                }
                if(count==1){
                    result += head - tail + 1;
                }
            }
            result %= 1_000_000_007;
        }
        return result;
    }



Get one-to-one training from Google Facebook engineers

Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.

Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.