3
\$\begingroup\$

Problem statement

Given a string \$S\$, find the number of "unordered anagrammatic pairs" of substrings.

Input Format

First line contains \$T\$, the number of testcases. Each testcase consists of string \$S\$ in one line.

Constraints

\$1 \leq T \leq 10\$

\$2 \leq length(S) \leq 100\$

String \$S\$ contains only the lowercase letters of the English alphabet.

Output Format

For each testcase, print the required answer in one line.

Sample Input#00

2

abba

abcd

Sample Output#00

4

0

Sample Input#01

5

ifailuhkqq

hucpoltgty

ovarjsnrbf

pvmupwjjjf

iwwhrlkpek

Sample Output#01

3

2

2

6

3

Explanation

Sample00

Let's say \$S[i,j]\$ denotes the substring \$S_i, S_i+1,\ldots ,S_j\$ .

testcase 1:

For \$S=abba\$, anagrammatic pairs are: \$\lbrace S[1,1],S[4,4]\rbrace ,\lbrace S[1,2],S[3,4]\rbrace ,\lbrace S[2,2],S[3,3]\rbrace, \lbrace S[1,3],S[2,4]\rbrace \$.

testcase 2:

No anagrammatic pairs.

My introduction of algorithm:

This algorithm was my most favorite string algorithm in 2016, I did study a lot of code submissions using C#. In January 2017, I read Sherlock and anagrams on this site, started to practice again and again, tried a few things on Hackerrank online judge. In terms of time complexity, the editorial note on Hackerrank gives some analysis, I am also curious to know if I miss something important there.

I learned to stay on this site and work hard on every practice to get the chance to be the best.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

class Solution
{  
   public class HashedAnagramString
   {
    /*
     * Make sure that two anagram strings will have some hashed code
     * 
     * @frequencyTable - Dictionary<char, int>
     * The frequency table has to be sorted first and then construct 
     * a string with each char in alphabetic numbers concatenated by 
     * its occurrences. 
     * 
     */
    public static int GetHashedAnagram(Dictionary<char, int> frequencyTable)
    {
        // build frequency table dynamically, how many time? O(n*n), n 
        // is the string's length
        StringBuilder key = new StringBuilder();

        foreach (var item in frequencyTable.OrderBy(s => s.Key))
        {
            key.Append(item.Key + item.Value.ToString());
        }

       return key.ToString().GetHashCode();
    }        
  }

  static void Main(String[] args)
  {
    ProcessInput();
    //RunSampleTestcase(); 
  }

  public static void RunSampleTestcase()
  {
    var hashedAnagramsDictionary = ConstructHashedAnagramsDictionary("abba");

    var pairs = CalculatePairs(hashedAnagramsDictionary);

    Debug.Assert(pairs == 4); 
  }

  public static void ProcessInput()
  {
    var queries = int.Parse(Console.ReadLine());

    while (queries-- > 0)
    {
        var input = Console.ReadLine();

        var hashedAnagramsDictionary = ConstructHashedAnagramsDictionary(input);

        Console.WriteLine(CalculatePairs(hashedAnagramsDictionary));
    }
  }

  /*
   * What should be taken cared of in the design? 
   * Time complexity: 
   * 3 for loops 
   * first loop, loop on the substring's length
   * second loop, loop on the substring's start position
   * third loop, go over each char in the substring to build a 
   * frequency table first; and then
   * update hashed anagram counting dictionary - a statistics, basically 
   * tell the fact like this:
   * For example, test case string abba, 
   * substring ab -> hashed key a1b1, value is 2, because there are 
   * two substrings: "ab","ba" having hashed key: "a1b1"
   * Here are all possible hashed keys: 
   * a1   - a, a, 
   * b1   - b, b
   * a1b1 - ab, ba
   * b2   - bb
   * a1b2 - abb, bba
   * a2b2 - abba
   * 
   */
  public static Dictionary<int, int> ConstructHashedAnagramsDictionary(string input)
  {        
    var hashedAnagramsDictionary  = new Dictionary<int,  int>();  

    var length  = input.Length;

    for (var substringLength = 1; substringLength < length; substringLength++)
    {
        for (var index = 0; index <= length - substringLength; index++)
        {
            var frequencyTable = new Dictionary<char, int>();                

            // build frequency table dynamically, how many time? O(n*n), 
            // n is the string's length
            for (var start = index; start < index + substringLength; start++)
            {
                char c = input[start];
                if (frequencyTable.ContainsKey(c))
                {
                    frequencyTable[c]++;
                }
                else
                {
                    frequencyTable.Add(c, 1);
                }
            }

            var key = HashedAnagramString.GetHashedAnagram(frequencyTable);

            if (hashedAnagramsDictionary.ContainsKey(key))
            {
                hashedAnagramsDictionary[key]++;
            }
            else
            {
                hashedAnagramsDictionary.Add(key, 1);
            }
        }             
    }

    return hashedAnagramsDictionary;
  }

 /*
  * The formula to calculate pairs
  * For example, test case string abba, 
  * substring ab -> hashed key a1b1, value is 2, because there are 
  * two substrings: "ab","ba" having hashed key: "a1b1"
  * Here are all possible hashed keys: 
  * a1   - a, a, 
  * b1   - b, b
  * a1b1 - ab, ba
  * b2   - bb
  * a1b2 - abb, bba
  * a2b2 - abba
  * So, how many pairs? 
  * should be 4, from 4 hashed keys: a1, b1, a1b1 and a2b2
  */
  public static int CalculatePairs(Dictionary<int, int> hashedAnagrams)
  {
    // get pairs
    int anagrammaticPairs = 0;

    foreach (var count in hashedAnagrams)
    {
        anagrammaticPairs += count.Value * (count.Value - 1) / 2;
    }

    return anagrammaticPairs; 
  }
}
\$\endgroup\$
  • \$\begingroup\$ The code is quite good. Not very knowledgeable in coding style and so on, but just a suggestion: It is possible to reduce the complexity of ConstructHashedAnagramsDictionary from N^3 to N^2, can you figure out how? \$\endgroup\$ – Raziman T V Jan 23 '17 at 10:39
  • \$\begingroup\$ @RazimanT.V., you asked the good question. I did study on this issue, there are N^2 substring, N is the string of length, each operation has to go over each char in the substring once, that is another O(N) operations, every though there are only 26 alphabetic numbers. So, it is not possible to make it O(N^2) if every substring is computed once roughly. \$\endgroup\$ – Jianmin Chen Jan 24 '17 at 17:55
  • 1
    \$\begingroup\$ You can convert to N^2 by changing the order of loops and processing substrings smartly. Try to think about it. \$\endgroup\$ – Raziman T V Jan 24 '17 at 18:00
  • 1
    \$\begingroup\$ @RazimanT.V., I think that it is same idea as Leetcode 238 Product of array except itself. We take advantage of alphabetic size is limited and constant, 26 chars, and then work with substring (denote Si) starting from 0 to i, 0 < i < n ( n is string's length) to calculate frequency table, and any substring starting from i and ending j can be Sj's frequency table - Si's frequency table for those 26 alphabetic numbers. \$\endgroup\$ – Jianmin Chen Jan 24 '17 at 21:16
  • 1
    \$\begingroup\$ So, the preprocessed frequency table size is O(N) ( N is the length of string) instead of O(N^2) based on each of substrings. For any of substrings, there are only 26 calculation to compute for each alphabet number, so the time complexity goes to O(26N^2) = O(n^2). \$\endgroup\$ – Jianmin Chen Jan 24 '17 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.