CODEWITHSUNDEEP
javastringalgorithmperformancechar
Yone
Yone

Reputation: 2134

Count characters ocurrence in string in a perfomant way?‽?

I am doing the following programming exercise: Numericals of a String. The statement is:

You are given an input string.

For each symbol in the string if it's the first character occurence, replace it with a '1', else replace it with the amount of times you've already seen it...

But will your code be performant enough? Examples:

input   =  "Hello, World!"
result  =  "1112111121311"

input   =  "aaaaaaaaaaaa"
result  =  "123456789101112"

There might be some non-ascii characters in the string.

Note: there will be no int domain overflow (character occurences will be less than 2 billion).

I have written the following answer:

import java.util.*;
import java.util.stream.*;
public class JomoPipi {
  public static String numericals(String s) {
    System.out.println("s: "+s);
    Map<String, Long> ocurrences = Arrays.stream(s.split("")).
                                    collect(Collectors.groupingBy(c -> c,
                                    Collectors.counting()));
    System.out.println("ocurrences: "+ocurrences.toString());                                    
    StringBuilder result = new StringBuilder();                                    
    for(int i = s.length()-1; i >= 0; i--){
      String c = String.valueOf(s.charAt(i));
      result.append(ocurrences.get(c) + " ");
      ocurrences.put(c, ocurrences.get(c)-1);
    }
    System.out.println("result: "+result.toString());
    String[] chars = result.toString().split(" ");
    Collections.reverse(Arrays.asList(chars));
    String sorted = String.join("",chars);
    System.out.println("sorted: "+sorted);
    return sorted;
  }
}

However it times out (execution time is above 16000 ms), when input string is big.

To see how it works there is a trace with a very small input string:

s: Hello, World!
result: 1 1 3 1 2 1 1 1 1 2 1 1 1 
sorted: 1112111121311

Besides, I have also written the following alternative answer:

import java.util.*;
import java.util.stream.*;
public class JomoPipi {
  public static String numericals(String s) {
    System.out.println("s: "+s);
    Map<String, Long> ocurrences = Arrays.stream(s.split("")).
                                    collect(Collectors.groupingBy(c -> c,
                                    Collectors.counting()));
    String[] result = new String[s.length()];                                   
    for(int i = s.length()-1; i >= 0; i--){
      String c = String.valueOf(s.charAt(i));
      result[i] = String.valueOf(ocurrences.get(c));
      ocurrences.put(c, ocurrences.get(c)-1);
    }
    System.out.println("result: "+Arrays.toString(result));
    return String.join("",result);
  }
}

Even so, it stills timing out.

Here is a trace with a small input string:

s: Hello, World!
result: [1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 3, 1, 1]

How could we improve the solution? What algorithm would perform better enough to handle very big input strings? Where is the bottleneck we should debug and avoid, to improve this answer?

To try to solve it by myself I have read:

EDIT: Here we have an answer based on @khelwood suggestion:

import java.util.*;
import java.util.stream.*;
public class JomoPipi {
  public static String numericals/*🔡->🔟*/(String s) {
    Map<String, Integer> ocurrences = new HashMap<String,Integer>();
    StringBuilder result = new StringBuilder();
    for(int i = 0; i < s.length(); i++){
      String c = String.valueOf(s.charAt(i));
      ocurrences.putIfAbsent(c, 0);
      ocurrences.put(c,ocurrences.get(c)+1);
      result.append(ocurrences.get(c));
    }
    return result.toString();
  }
}

Upvotes: 2

Views: 465

Answers (1)

Elliott Frisch
Elliott Frisch

Reputation: 201429

I think you were on the right track with a Map, but your key type should be Character and your count type Integer. I think you went wrong when you then reversed and sorted your result. Also, your code would be easier to read without the stream (and a key part of writing fast code, is to write dumb code). For example,

public static String numericals(String s) {
    int len = s.length();
    Map<Character, Integer> occurrences = new HashMap<>(); // ocurrences
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len; i++) {
        char ch = s.charAt(i);
        int count = occurrences.getOrDefault(ch, 0) + 1;
        occurrences.put(ch, count);
        sb.append(count);
    }
    return sb.toString();
}

And then to test it

public static void main(String[] args) {
    String[] input = { "Hello, World!", "aaaaaaaaaaaa" };
    String[] output = { "1112111121311", "123456789101112" };
    for (int i = 0; i < input.length; i++) {
        String result = numericals(input[i]);
        System.out.printf("%s %b%n", result, result.equals(output[i]));
    }
}

Which outputs

1112111121311 true
123456789101112 true

Upvotes: 2

Related Questions