Sherlock and Anagrams

Question

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.

Output Format

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

Sample Input#00

2
abba
abcd

Sample Output#00

4
0

In the below code I am finding all the possible sub strings and then checking all the pairs of equal length to check if they are anagrams or not.

public class Solution {
    private static int N = 26;

    private static boolean isAnagram(String a, String b) {
        int []countA = new int[N];
        int []countB = new int[N];

        for (char c : a.toCharArray()) {
            countA[c - 'a']++;
        }

        for (char c : b.toCharArray()) {
            countB[c - 'a']++;
        }

        for (int i = 0; i < N; i++) {
            if (countA[i] != countB[i]) {
                return false;
            }
        }

        return true;
    }

    private static int getPairsCount(String text) {
        int count = 0;
        int length = text.length();

        List<String> subsets = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            for (int j = 1; j <= length - i; j++) {
                subsets.add(text.substring(i, i + j));
            }
        }

        for (int i = 0; i < subsets.size(); i++) {
            for (int j = i + 1; j < subsets.size(); j++) {
                String s1 = subsets.get(i);
                String s2 = subsets.get(j);
                if (i != j &&
                    s1.length() == s2.length() &&
                    isAnagram(s1, s2)) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();

        for (int i = 0; i < N; i++) {
            System.out.println(getPairsCount(s.next()));
        }
    }
}

Questions:

I have to agree it took me a lot of time to find the above solution because I spend a lot of time into finding the linear algorithm. For this solution I think that it's \$\mathcal{O}(n^3)\$ solution which feels slow to me.

I need to know how to approach problems like these? when to know that there can't be any linear algorithm possible?

Answer 1

You can speed up your code by changing changing strategy. The overall goal is to determine the occurrence counts (frequencies) of all possible 'normalised' substrings of the given input, and then to use these counts for computing the number of pairings.

'Normalised' means processed in a way that gives all anagrams the same physical representation, either by sorting the substrings on character code (which is \$\mathcal{O}(N log N)\$ where \$N\$ is the length of the string to be normalised) or by frequency counting (which is \$\mathcal{O}(N)\$).

Byte-sized variables are sufficient for frequency counting since inputs are no longer than 100 characters, which means the normalised form of any string will by an array of 26 bytes. Which version is better depends on the (unknown) input distribution, but normalisation by sorting is simpler to arrange in Java than frequency counting and hence preferrable.

The number of possible substrings of a string of length \$K\$ is \$K * \frac{(K + 1)}{2}\$, normalisation was discussed above, and dictionary lookups are amortised \$O(M)\$ where \$M\$ is the length of what's being looked up. Hence overall complexity of this simple approach is quadratic, modulo a logarithmic component if normalisation is done by sorting instead of frequency counting (but that doesn't change the overall picture much), and modulo an additional linear factor if you look up variable-length substrings instead of fixed-length frequency count arrays.

Given the shortness of the inputs, this simple solution should be fast enough to be accepted. If the envelope needs to be pushed then there is no ready-made recipe. The only thing safe to say is that enumerating substrings one by one will invariably add a quadratic component to the complexity.

Also, the constant factor dropped by the asymptotic can be several orders of magnitude depending on how smart you go about enumerating the normalised forms of all substrings. For example, you could enumerate all substrings starting at a given position by starting with the character at that position, adding it to the map, inserting the next character in sorted order, adding that to the map, and so on. That would make the cost of a single normalisation \$\mathcal{O}(log N)\$ instead of the \$\mathcal{O}(N log N)\$ for taking a substring and sorting it, or \$\mathcal{O}(1)\$ if frequency counting is used. A similar strategy can be used with frequency counts. This incremental approach is what makes the overall complexity quadratic instead of cubic (but beware of var-length strings as discussed above).

Also, the are data structures like tries that can handle operations on substrings in linear time instead of quadratic, but the algorithms get really involved. You really need to know your basic data structures and algorithms inside out in order to see whether they can help you with a given problem. I'm not certain whether Sherlock and Anagrams can be solved with less than quadratic complexity without resorting to tries.

However, as a general strategy you should take the problem and look for ways of not doing work, to strip the problem down to its irreducible core of work that cannot possibly be avoided. And remember that counting things can be easier computationally speaking than enumerating them and incrementing a count. E.g. if you know that there are \$K\$ somethings then you can compute the number of their possible pairings in \$\mathcal{O}(1)\$ with a bit of combinatorics, instead of enumerating and counting at a cost of \$\mathcal{O}(K^2)\$. Another classic example is the length of the longest common subsequence of two strings which can be computed in \$\mathcal{O}(N^2)\$ even though the number of possible common subsequences is exponential.

Answer 2

Finalize constants

    private static int N = 26;

This could be

    private static final int N = 26;

Then if you accidentally set N to some other value, it will show an error at compilation time. As is,

        N = 25;

would only sometimes cause a runtime error. I.e. only if there is a z in the input.

Remove duplicate code

    private static boolean isAnagram(String a, String b) {
        int []countA = new int[N];
        int []countB = new int[N];

        for (char c : a.toCharArray()) {
            countA[c - 'a']++;
        }

        for (char c : b.toCharArray()) {
            countB[c - 'a']++;
        }

        for (int i = 0; i < N; i++) {
            if (countA[i] != countB[i]) {
                return false;
            }
        }

        return true;
    }

This has duplicate code. Consider the following alternative.

    private static int[] countLetters(String s) {
        int[] counts = new int[N];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }

        return counts;
    }

    private static boolean isAnagram(int[] countsA, int[] countsB) {
        for (int i = 0; i < countsA.length; i++) {
            if (countsA[i] != countsB[i]) {
                return false;
            }
        }

        return true;
    }

    private static boolean isAnagram(String a, String b) {
        return isAnagram(countLetters(a), countLetters(b));
    }

Naming nitpick

    private static int getPairsCount(String text) {

Calling a method getWhatever implies that there is a field named whatever that it returns. Consider

    private static int countPairs(String text) {

Now we expect that we are counting something related to text.

Do math once

            for (int j = 1; j <= length - i; j++) {
                subsets.add(text.substring(i, i + j));

Consider

            for (int j = i + 1; j <= length; j++) {
                subsets.add(text.substring(i, j));

This changes a subtraction to an addition in the loop definition.

And it removes an addition from each iteration of the loop. Why do i + j if you can just put the right value in j?

Don't repeat work

    private static int getPairsCount(String text) {
        int count = 0;
        int length = text.length();

        List<String> subsets = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            for (int j = 1; j <= length - i; j++) {
                subsets.add(text.substring(i, i + j));
            }
        }

        for (int i = 0; i < subsets.size(); i++) {
            for (int j = i + 1; j < subsets.size(); j++) {
                String s1 = subsets.get(i);
                String s2 = subsets.get(j);
                if (i != j &&
                    s1.length() == s2.length() &&
                    isAnagram(s1, s2)) {
                    count++;
                }
            }
        }
        return count;
    }

Each time you call isAnagram, it counts the letters again in this code. Consider:

    private static int countPairs(String text) {
        int length = text.length();
        List<int[]> subsets = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j <= length; j++) {
                subsets.add(countLetters(text.substring(i, j)));
            }
        }

        int count = 0;
        for (int i = 0; i < subsets.size(); i++) {
            int[] countsA = subsets.get(i);
            for (int j = i + 1; j < subsets.size(); j++) {
                int[] countsB = subsets.get(j);
                if (countsA.length == countsB.length && isAnagram(countsA, countsB)) {
                    count++;
                }
            }
        }

        return count;
    }

This counts the letters for each string once.

Since subsets.get(i) has the same value regardless of j, we can do it outside the j loop. We don't have to repeat it on each iteration of the inner loop.

Since j increments from i + 1 and up, it can never equal i. So no need to check i != j.

Remember when we rewrote isAnagram to separate counting the letters from comparing counts? We can make use of that here. Rather than storing substrings, we can just store counts. Now we no longer have to recount the string on each comparison.

Complexity analysis

Your original code is \$\mathcal{O}(n^5)\$ where \$n\$ is the length of the string. This is because subsets is \$\mathcal{O}(n^2)\$ in size and you iterate over it twice with a linear time call to isAnagram inside that.

This variant reduces that to \$\mathcal{O}(n^4)\$, as isAnagram is now constant time relative to the length of the string.

Note that the first pair of loops is now \$\mathcal{O}(n^3)\$, but that doesn't matter if the second set is \$\mathcal{O}(n^4)\$.

Advanced

We throw all the substrings in the same bucket and compare each to each. However, if the length is not equal, we don't need to compare. So we could put different length substring counts in different buckets. Then we'd only have to compare within a bucket. This is \$\mathcal{O}(n^3)\$ as there are \$\mathcal{O}(n)\$ buckets of \$\mathcal{O}(n)\$ items each. So comparing in a bucket is \$\mathcal{O}(n^2)\$ which you do \$\mathcal{O}(n)\$ times.

It won't change the complexity analysis, but you can potentially increases the efficiency of isAnagram by implementing a hash code. So we only need to do a full comparison if the hashcodes are equal. We could calculate the hashcode at the same time as we count the letters.

Answer 3

Algorithm with time complexity \$\mathcal{O}(26*N*N)\$, \$N\$ is the string's length

To answer the question about time complexity \$\mathcal{O}(N^3)\$ implementation in the question, I propose an idea similar to Leetcode 238 Product of array except itself, to achieve optimal time complexity, lower one level. Related to sherlock and anagrams, the time complexity can be lowered from \$\mathcal{O}(N^3)\$ to \$\mathcal{O}(N^2)\$.

Here is more detail. 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, in other words, calculate all \$\mathcal{O}(N^2)\$ substrings' frequencey table use only \$N\$ substrings' preprocessed frequency table. Any substring starting from \$i\$ and ending \$j\$'s frequency table can be \$Sj'\$s frequency table \$-\$ \$Si\$'s frequency table for those \$26\$ alphabetic numbers.

So, the preprocessed frequency table size is \$\mathcal{O}(N)\$ ( \$N\$ is the length of string) instead of \$\mathcal{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 \$\mathcal{O}(26N^2) \subseteq \mathcal{O}(N^2)\$.

We also need to discuss the time complexity to build a dictionary with key and value, where key is associated with frequency table hashed key, value is how many substring with the hashed key. Since the hashed key cannot be more than substring number in total, the time to build the dictionary (refer to function ConstructHashedAnagramsDictionary's variable hashedAnagramsDictionary). So the time complexity is \$\mathcal{O}(N^2)\$.

To save time, I share my C# practice code, you can run it through Hackerrank easily. C# source code link is here.

Hackerrank problem statement and submission link is here.

1. Preprocess a Size \$\mathcal{O}(N)\$ frequency table

First, build a preprocessed frequency table:

/*
 * Prepare fequence table for N substring which starts from index 0
 * Do not need include all other substrings as we know there are total O(N*N) substrings. 
 * 
 * Work on one small test case:
 * "abcd"
 * so the frequency table for substrings, all starts from index = 0:
 * a
 * ab
 * abc
 * abcd
 * Only for those 4 substrings, not all of them. 
 * 
 * Time complexity:  O(N * N)
 * Space complexity: O(26*N), N is the string's length
 */
public static int[][] PrepareFequencyTableForOnlyNSubstring(string input)
{
    if (input == null || input.Length == 0)
    {
        return null;
    }

    int length = input.Length;
    int[][] frequencyTables = new int[length][];

    for (int i = 0; i < length; i++)
    {
        frequencyTables[i] = new int[26];
    }

    for (int start = 0; start < length; start++) // go over the string once from the beginning
    {
        char current = input[start];
        int charIndex = current - 'a';

        for (int index = start; index < length; index++)
        {
            frequencyTables[index][charIndex]++;
        }
    }

    return frequencyTables;
}  

2. Calculate frequency table for any substring

/*
 * 
 * @start - substring' start position in the original string
 * @length - substring's length
 * Just a simple minus calculation for each alphabet number. 
 */
 public static int[] CalculateSubstringFequencyDiff(int[][] fequencyTableMemo, int start, int length)
 {
    const int size = 26;
    int[] difference = new int[size];

    for (int i = 0; i < size; i++)
    {
        difference[i] = fequencyTableMemo[start + length - 1][i];
        if (start > 0)
        {
            difference[i] -= fequencyTableMemo[start-1][i];
        }
    }

    return difference;
 }

3. C# implemented algorithm with time complexity \$\mathcal{O}(N^2)\$

Code passes all the test cases. Please read the following.

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 string GetHashedAnagram(int[] frequencyTable)
    {
        StringBuilder key = new StringBuilder();

        for (int i = 0; i < 26; i++)
        {
            int value = frequencyTable[i];
            if (value > 0)
            {
                char c = (char)(i + 'a');
                key.Append(c.ToString() + value);
            }
        }

        return key.ToString();
    }
  }

  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));
    }
  }

/*
 * Prepare fequence table for N substring which starts from index 0
 * Do not need include all other substrings as we know there are total O(N*N) substrings. 
 * 
 * Work on one small test case:
 * "abcd"
 * so the frequency table for substrings, all starts from index = 0:
 * a
 * ab
 * abc
 * abcd
 * Only for those 4 substrings, not all of them. 
 * 
 * Time complexity:  O(N * N)
 * Space complexity: O(26*N), N is the string's length
 */
public static int[][] PrepareFequencyTableForOnlyNSubstring(string input)
{
    if (input == null || input.Length == 0)
    {
        return null;
    }

    int length = input.Length;
    int[][] frequencyTables = new int[length][];

    for (int i = 0; i < length; i++)
    {
        frequencyTables[i] = new int[26];
    }

    for (int start = 0; start < length; start++) // go over the string once from the beginning
    {
        char current = input[start];
        int charIndex = current - 'a';

        for (int index = start; index < length; index++)
        {
            frequencyTables[index][charIndex]++;
        }
    }

    return frequencyTables;
}    

/*
 * What should be taken cared of in the design? 
 * Time complexity: O(26 * N * N), N is the string length. 
 * 
 * 
 * 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.
 * 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)               
 * 
 * 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
 * 
 * Time complexity is O(N^2), not O(N^3). 
 */
public static Dictionary<string, int> ConstructHashedAnagramsDictionary(string input)
{
    var hashedAnagramsDictionary = new Dictionary<string, int>();

    var length = input.Length;

    // frequency table memo is using time O(N * N)
    var fequencyTableMemo = PrepareFequencyTableForOnlyNSubstring(input);

    for (int start = 0; start < length; start++)
    {
        for (int substringLength = 1; start + substringLength <= length; substringLength++)
        {
            var frequencyData = CalculateSubstringFequencyDiff(fequencyTableMemo, start, substringLength);

            var key = HashedAnagramString.GetHashedAnagram(frequencyData);

            // At most there are O(N*N) entry in the dictionary, go over once
            if (hashedAnagramsDictionary.ContainsKey(key))
            {
                hashedAnagramsDictionary[key]++;
            }
            else
            {
                hashedAnagramsDictionary.Add(key, 1);
            }
        }
    }

    return hashedAnagramsDictionary;
}

/*
* 
* @start - substring' start position in the original string
* @length - substring's length
* Just a simple minus calculation for each alphabet number. 
*/
public static int[] CalculateSubstringFequencyDiff(int[][] fequencyTableMemo, int start, int length)
{
    const int size = 26;
    int[] difference = new int[size];

    for (int i = 0; i < size; i++)
    {
        difference[i] = fequencyTableMemo[start + length - 1][i];
        if (start > 0)
        {
            difference[i] -= fequencyTableMemo[start-1][i];
        }
    }

    return difference;
}

/*
 * 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<string, int> hashedAnagrams)
{
    // get pairs
    int anagrammaticPairs = 0;

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

    return anagrammaticPairs;
  }
}