Error in finding count of anagrams of a large substring

Admin 1
Viewed 132

I am trying to check and count of anagrams pairs for every sub-strings of a input string.

For example, if the input string is mom, then anagram pairs are m,m and mo,om.

The code works good and passed for the three strings test cases. But the code gets terminated due to timeout constraints for the long input strings like : 

ifailuhkqqhucpoltgtyovarjsnrbfpvmupwjjjfiwwhrlkpekxxnebfrwibylcvkfealgonjkzwlyfhhkefuvgndgdnbelgruel

I tried and researched for the issue but I am struck with this error. Ccan you guys kindly help me to resolve the issue with your suggestions?

Providing code below:

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

public class Solution {

    // Complete the sherlockAndAnagrams function below.
    static int sherlockAndAnagrams(String s) {

        for(int i=0; i<s.length(); i++){
            for(int j=i+1; j<=s.length(); j++){
                sArray[index] = s.substring(i,j);
                index++;
                //System.out.println(s.substring(i,j));
                //System.out.println(Arrays.toString(sArray));
            }
        }
        for(int i=0; i<sArray.length; i++){
            for(int j=i; j< sArray.length; j++){
                if(i != j){
                if(null == sArray[i])
                break;
                if(null == sArray[j])
                break;
                char[] sArray1 = sArray[i].toCharArray();
                char[] sArray2 = sArray[j].toCharArray();
                //System.out.println(sArray1);
                //System.out.println(sArray2);
                //int index_str = 0;
                Hashtable<Character, Integer>sHash1 = new Hashtable<Character, Integer>();
                Hashtable<Character, Integer>sHash2 = new Hashtable<Character, Integer>();
                for (int k = 0; k < sArray1.length; k++) { 

                    if (sHash1.get(sArray1[k]) == null) { 

                        sHash1.put(sArray1[k], 1); 
                    } 
                    else { 
                        Integer c = (int)sHash1.get(sArray1[k]); 
                        sHash1.put(sArray1[k], ++c); 
                    } 
                } 

                // Mapping second String 
                for (int l = 0; l < sArray2.length; l++) { 

                    if (sHash2.get(sArray2[l]) == null) 
                        sHash2.put(sArray2[l], 1); 
                    else { 

                        Integer d = (int)sHash2.get(sArray2[l]); 
                        sHash2.put(sArray2[l], ++d); 
                    } 
                } 

                if(sHash1.equals(sHash2)){
                    count++;
                }
                }
            }
        }

        }*/
        //System.out.println(sHash);
        return count;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter  = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int qItr = 0; qItr < q; qItr++) {
            String s = scanner.nextLine();

            int result = sherlockAndAnagrams(s);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}
java
1 Answers

Here is one part of your problem:

    for(int i=0; i<s.length(); i++){
        for(int j=i+1; j<=s.length(); j++){
            sArray[index] = s.substring(i,j);
            index++;
        }
    }

the substring methods returns a new string object. you are allocating memory for every possible substring.

The number of new string objects you create can be roughly calculated with the formula: n*(n+1)/2. That thing grows very fast. For example for n = 10 it is at 55, for n = 50 it is already at 1275.

So for long strings your code may already crash because out of memory here.

Here is the second part of your problem:

    for(int i=0; i<sArray.length; i++){
        for(int j=i; j< sArray.length; j++){

you compare every substring with every substring. The number of iterations can again be calculated with n*(n+1)/2. When you have a string of length 50 that is over 1000 substrings that is over 500000 iterations.

Furthermore: in every iteration you create two char arrays and two hashtables. At least they are discarded after every loop so memory should not be an issue. but speed might.

I think this is why you get your timeout for long strings.

here a not complete set of hints on how to fix this:

  • in the first big loop just save the indexes (i and j) for further use instead of allocating an entire new string for every substring.
  • in the second big loop you are redoing the calculation for a substring repeatedly. for example you are comparing substring 0 to 1, 2, 3, ... then you are comparing substring 1 to 2, 3, ... so substring 2 is already calculated twice. the last substring will be calculated repeatedly for every substring before it. you can try to save the result to prevent recalculation. but that will again eat memory. it is always a trade off of memory and calculation cycles.
  • maybe you can do without the char arrays. you can iterate over a string just like an array.
  • maybe you can do without the hashtable. just compare the characters directly.

I couldn't compile your code so i couldn't verify my assumptions. There is a } too many and sArray does not seem to be declared. I was too lazy to try to fix that.

Links:

user_3608990
Related