Codeforces 50B Choosing Symbol Pairs Solution & Explanation

Difficulty : 1500

Problem Description

There is a given string S consisting of N symbols. Your task is to find the number of ordered pairs of integers i and j such that

1. 1 ≤ i, j ≤ N

2. S[i] = S[j], that is the i-th symbol of string S is equal to the j-th.

Input

The single input line contains S, consisting of lowercase Latin letters and digits. It is guaranteed that string S in not empty and its length does not exceed 10⁵.

Output

Print a single number which represents the number of pairs i and j with the needed property. Pairs (x, y) and (y, x) should be considered different, i.e. the ordered pairs count.

Examples

Solution

We can definitely use two for loops to check each index, and if their values are equal. However, that would waste too much time, resulting in an O(n²) time complexity.

C# Solution

Solution1

string txt = Console.ReadLine();

Dictionary<char,int> dict =   new Dictionary<char,int>();

foreach(var a in txt)
{
    if (!dict.ContainsKey(a))
    {
        dict.Add(a, 1);
    }
    else
    {
        dict[a] = dict[a]+1;
    }
}

double res = 0;
foreach(var item in dict)
{
    res+= Math.Pow(item.Value,2);
}

Console.Write((long)res);

We can’t use an integer as the result because some test cases may exceed its limit.

Conclusion

This problem is from codeforces contest – Dashboard – Codeforces Beta Round 47 – Codeforces

You can find the solution for the first problem here –Codeforces 50A Domino piling Solution & Explanation

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks you~~

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know !!

The problem link : Problem – 50B – Codeforces

Random Codeforces Posts