Find the number of unordered anagramic pairs of substrings

Question

I am trying to solve the following question: https://www.hackerrank.com/challenges/sherlock-and-anagrams

This is my code

import java.util.*;
public class Solution {

public static boolean check(String s1,String s2)
{

    int [] count1 = new int[26];
    for( int i = 0; i < s1.length(); i++ )
    {
        char ch1 = s1.charAt(i);
        count1[ch1-'a']++;
    }

    int [] count2 = new int[26];
    for( int i = 0; i < s2.length(); i++ )
    {
        char ch2 = s2.charAt(i);
        count2[ch2-'a']++;
    }

    int count =0;
    for(int j=0;j<26;j++)
    {
        count = count + Math.abs(count1[j]-count2[j]);
    }

    if(count ==0)
            return true;
    else return false;
}
public static void main(String[] args) {

    String s,sub;
    int i,c,len;
    List<String> all = new ArrayList<>();

    Scanner in = new Scanner(System.in);
    int t = Integer.parseInt(in.nextLine());

      while((t--)>0)
    {
          s  = in.nextLine();
          len = s.length();   
       for( c = 0 ; c < len ; c++ )
       {
           for( i = 1 ; i <= len - c ; i++ )
          {
             sub = s.substring(c, c+i);
            all.add(sub);
          }
       }

      String[] arr = new String[all.size()];
      for( i = 0; i < all.size(); i++) 
              arr[i] = all.get(i);

          int l=0;
          for (int m=0;m<arr.length;m++)
          {
              for(int n=m+1;n<arr.length;n++)
               {
                  if(check(arr[m],arr[n]))
                         l++;
              }
          }

          System.out.println(l);all.clear();
    }

}
}

My code worked for few test cases which have small strings but failed to work if string size is too big

Sample input

5
ifailugtyovhdfuhdouarjsnrbfpvmupwjjjfiwneogwnoegnoegneognoewhrlkpekxxnebfrwibylcvkfealgonjkzw
gffryqktmwocejbrexfidpjfgrrkpowoxwggxaknmltjcpazgtnakcfbveieivoenwvpnoevvneocogzatyskqjyorcftw
uqlzvuzgkwhkkrrfpwarkckansgabfclzgnumdrojexnofeqjnqnxwidhbvbenevun9evnnv9euxxhfwargwkikjq
sygjxynvofnvirarcoacwnhxyqlrviikfuiuotifznqmzpjrxycnqkeibvibvewioebvitkryutpqvbgbgthfges
mkenscyiamnwlpxytkndjsygifmqlqibxxqlauxamfviftquntvkwppxrzuncyenavebiobeviobeiobeibvcfivtigv

My Output

4s : Terminated due to timeout

is there any better way to solve it or to change the existing code so that executed time is within 4mins

What did you learn from my answer on [your previous question](http://stackoverflow.com/q/29191074/1679863)? You've repeated the same mistake again. — Rohit Jain, Mar 22 '15 at 06:24
You are comparing each substring with each other substring. Anagramatic substrings have the same number of letters. You'll have to redesign the code in the `main` method. Also, `check` can be made much faster. (There's a couple of '9' in the second long input string.) — laune, Mar 22 '15 at 09:07

score 4 · Accepted Answer · answered May 02 '15 at 03:55

You can check out this link. It is explained very well here.

I think that you are storing all substrings and then searching for the anagram pair because of that space complexity of your code is very much. So you can improve that. You can also reduce the number of operations in your check function by returning false at the very first point where they mismatch.

I have implemented the above problem in c++. Here is my code:

#define MAX 26
bool isAnagram(int *count1, int *count2) {
    for(int i = 0; i < MAX; i++) {
        if(count1[i] != count2[i])
            return false;
    }
    return true;
}

int findPair(string str, int start, char *tmp, int n) {
    int len = str.length();
    if(strlen(tmp) > len-start) {
        return 0;
    }

    int *count1 = new int[MAX];
    int *count2 = new int[MAX];
    int cnt = 0;
    int i;
    for(i = 0; i < MAX; i++) {
        count1[i] = 0; 
        count2[i] = 0;
    }

    for(i = 0; i < n && (start+i) < len; i++) {
        count1[tmp[i]-'a']++;
        count2[str[start+i]-'a']++;
    }

    int j;
    for(j = start + i; j < len; j++) {
        if(isAnagram(count1, count2)) {
            cnt++;
        }
        count2[str[start]-'a']--;
        count2[str[j]-'a']++;
        start++;
    }
    if(j == len) {
        if(isAnagram(count1, count2)) {
            cnt++;
        }
    }

    delete []count1;
    delete []count2;

    return cnt;
}

int countPairs(string str) {
    int n = str.length();
    if(n < 2) {
        return 0;
    }

    int cnt = 0;
    char *tmp = new char[n];
    for(int i = 0; i < n; i++) {
        int k = 0;
        for(int j = i; j < n; j++) {
            tmp[k] = str[j];
            tmp[k+1] = '\0';

            cnt += findPair(str, i+1, tmp, k+1);
            k++;
        }
    }
    delete []tmp;
    return cnt;
}

int main() {
    int t;
    cin>>t;

    while(t--) {
        string str;
        cin>>str;
        cout<<countPairs(str)<<endl;
    }

    return 0;
}

Awesome , it passed all the test cases in limited time – coder101 Jun 12 '15 at 20:15 — coder101, Jun 12 '15 at 20:15

score 1 · Answer 2 · answered Mar 26 '16 at 12:28

Apart from early termination. You can use a HashMap, the key being the length and the value being a list of substrings of the same length. Store the substrings and check only with elements inside the 'value'. Although you might think it works the same as early termination if the lengths are different, it makes a difference and doesn't give early termination problems.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int x=sc.nextInt();
        for(int k=0; k<x; k++){
            String str1=sc.next();
            HashMap<Integer,ArrayList<String>> sub= getSub(str1);
            int counter=0;
            for(int t=1; t<=str1.length(); t++){
                ArrayList<String> subsl= sub.get(t);
                for(int i=0; i<subsl.size()-1; i++){
                    for(int j=i+1; j<subsl.size(); j++){
                        if(isAnagram(subsl.get(j),subsl.get(i))){
                            counter++;
                        }
                    }   
                }
            }
            System.out.println(counter);
        }
    }
    public static HashMap<Integer,ArrayList<String>> getSub(String str1){
        HashMap<Integer,ArrayList<String>> ret= new HashMap<Integer,ArrayList<String>>();
        for(int i=0; i<str1.length(); i++){
            for(int j=i; j<str1.length(); j++){
                if(!ret.containsKey(str1.substring(i, j+1).length())){  
                    ArrayList<String> x= new ArrayList<String>();
                    x.add(str1.substring(i, j+1));
                    ret.put(str1.substring(i, j+1).length(), x);
                }
                else
                    ret.get(str1.substring(i, j+1).length()).add(str1.substring(i, j+1));
            }
        }
        return ret;
    }

    public static boolean isAnagram(String a1, String a2){
        int count1[]= new int[26];
        int count2[]= new int[26];
        if(a1.length()!=a2.length())
            return false;
        for(int i=0; i<a1.length(); i++){
            count1[(int)a1.charAt(i)-97]++;
            count2[(int)a2.charAt(i)-97]++;
        }
        for(int i=0; i<26; i++){
            if(count1[i]!=count2[i])
                return false;
        }
        return true;
    }
}

If you want to make it even faster, then change the HashMap to include an object with has the counts of all 26 alphabets. That'll obviously take more memory so you can have something intermediate with the length and say counts of letters a,b,c (or 3 such letters). To make the checking efficient, use bit manipulation to encode all these (length, count of a, count of b and count of c). Though take care to not exceed the number of bits for Integer.

score 0 · Answer 3 · answered Sep 29 '15 at 11:35

Try this. What I have done here is broken the string into two substrings and checked all the anagramic pairs of 1st string in the second.

for ex:abba

1st substring=a;

2nd substring=bba

now check all anagramic pairs of a in bba

import java.util.*;

public class SherlockAndAnagrams{

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int t=Integer.parseInt(sc.nextLine());
    while(t-->0){
        String s=sc.nextLine();
        int count=0;
        for(int i=0;i < s.length();i++){
            for(int k=i+1;k < s.length();k++){
                int num=anagram(s.substring(i,k),s.substring(i+1),s.substring(i,k).length());
                count=count+num;
            }
        }
        System.out.println(count);
    }
}
static int anagram(String s1,String s2,int len){
    int count = 0;

    char[] c1=s1.toCharArray();
    Arrays.sort(c1);
    String ss1=new String(c1);
    int length=s2.length();

    for(int i=0;i<length;i++){
        if(i+len<=length){
        String sub=s2.substring(i,i+len);
        char[] c2=sub.toCharArray();
        Arrays.sort(c2);
        String ss2=new String(c2);
        if(ss1.compareTo(ss2)==0)
            count++;
        }
    }
return count;
}

}

Find the number of unordered anagramic pairs of substrings

3 Answers3

Linked