StrengthOfPassword

这道题 https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/但是细节稍有不同 这题用nested for loop就可以解但会有test cases超时 需要用DP比较快就全能过了.

https://leetcode.com/discuss/interview-question/1481915/Amazon-or-OA-or-Count-distinct-characters-in-all-substrings https://www.tutorialspoint.com/count-unique-characters-of-all-substrings-of-a-given-string-in-cplusplus https://leetcode.com/discuss/interview-question/1564287/Amazon-or-OA-or-Strength-of-password/1143344 * https://www.geeksforgeeks.org/find-distinct-characters-in-distinct-substrings-of-a-string/

Approach: Take all possible sub-strings of the given string and use a set to check whether the current sub-string has been processed before. Now, for every distinct sub-string, count the distinct characters in it (again set can be used to do so). The sum of this count for all the distinct sub-strings is the final answer. Below is the implementation of the above approach:

class geeks
{
 
    // Function to return the count of distinct
    // characters in all the distinct
    // sub-strings of the given string
    public static int countTotalDistinct(String str)
    {
        int cnt = 0;
 
        // To store all the sub-strings
        HashSet<String> items = new HashSet<>();
 
        for (int i = 0; i < str.length(); ++i)
        {
 
            // To store the current sub-string
            String temp = "";
 
            // To store the characters of the
            // current sub-string
            HashSet<Character> ans = new HashSet<>();
            for (int j = i; j < str.length(); ++j)
            {
                temp = temp + str.charAt(j);
                ans.add(str.charAt(j));
 
                // If current sub-string hasn't
                // been stored before
                if (!items.contains(temp))
                {
 
                    // Insert it into the set
                    items.add(temp);
 
                    // Update the count of
                    // distinct characters
                    cnt += ans.size();
                }
            }
        }
 
        return cnt;
    }

Version 2: https://leetcode.com/discuss/interview-question/1481915/Amazon-or-OA-or-Count-distinct-characters-in-all-substrings

Idea : counting the contribution by each alphabet to the answer i.e, If a substring has multiple a's, only '1' is contributed by 'a' to the final count per each substring.

    int solve(char c, string s){ // Counts no.of substrings that contain atleast one of the characters as c.
        int cnt=0,n=s.length(),res=0;
        for(int i=0;i<n;i++){
            if(s[i]==c){
                res+=(cnt)*(cnt+1)/2;
                cnt=0;
            }
            else
                cnt++;
        }
        res+=(cnt)*(cnt+1)/2;
        return n*(n+1)/2 - res;
    }
    int countdistinct(string s) {
        int ans=0;
        for(char c='A';c<='Z';c++)
            ans+=solve(c,s);
        return ans;
    }