See http://stackoverflow.com/questions/32923969/whats-the-fastest-way-of-checking-if-one-string-contains-the-characters-of-anot/32924620?noredirect=1#comment53676778_32924620

Benchmark.java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.function.BiFunction;
import java.util.stream.Collectors;

public class Benchmark {
    private static final Random rd = new Random(System.currentTimeMillis());
    
    private static final int LENGTH_1 = 50000;
    private static final int LENGTH_2 = 5000000;
    private static final int LENGTH_3 = 50000000;
    
    public static void main(String[] args) {
        System.out.println("My version :");
        testAll(Benchmark::inneholdtDici);
        
        System.out.println("\nMax's parallel solution :");
        testAll(Benchmark::inneholdtMax);
    }
    
    public static void testAll(BiFunction<String, String, Boolean> inneholdt) {
        for (Integer lenA : Arrays.asList(LENGTH_1, LENGTH_2, LENGTH_3)) test(lenA, inneholdt);
    }
    
    public static boolean inneholdtDici(String a, String b) {
        if (b.length() > a.length()) return false;
    
        Map<Character, Integer> countChars = new HashMap<>();
        // in Java 8. For older versions, it is also easy but more verbose
        for (char ch : b.toCharArray()) countChars.put(ch, countChars.getOrDefault(ch, 0) + 1);
        for (char ch : a.toCharArray()) {
            Integer count = countChars.get(ch);
            if (count != null) {
                if (count == 1) countChars.remove(ch);
                else            countChars.put(ch, count - 1);
            }
            if (countChars.isEmpty()) return true;
        }
        return false;
    }
    
    public static boolean inneholdtMax(String a, String b) {
        // Here we are counting occurrences of characters in the string
        Map<Integer, Long> aCounted = a.chars().parallel().boxed().collect(Collectors.groupingBy(o -> o, Collectors.counting()));
        Map<Integer, Long> bCounted = b.chars().parallel().boxed().collect(Collectors.groupingBy(o -> o, Collectors.counting()));

        // Now we're checking if the second string contains all the characters from the first
        return bCounted.keySet().parallelStream().allMatch(
                x -> bCounted.getOrDefault(x, 0l) >= aCounted.getOrDefault(x, 0l)
        );
    }
        
    public static void test(int lenA, BiFunction<String, String, Boolean> inneholdt) {
        if (lenA < 1000) throw new IllegalArgumentException();
        
        int iterations = 5;
        for (int lenB = lenA / 1000; lenB <= lenA; lenB *= 10) { 
            long meanTimeMs = 0;
            for (int i = 0; i < iterations; i++) {
                String a = randomString(lenA);
                String b = randomString(lenB);
                
                long start = System.currentTimeMillis();
                inneholdt.apply(a, b);
                meanTimeMs += System.currentTimeMillis() - start;
            }
            System.out.printf("Mean time of %d ms with lenA = %d, lenB = %d\n", meanTimeMs / iterations, lenA, lenB);
        }
    }
    
    public static String randomString(int length) {
        char[] chars = new char[length];
        for (int i = 0; i < length; i++)
            chars[i] = (char) rd.nextInt(Character.MAX_VALUE);
        return new String(chars);
    }
}