A few words about java 8 performance, sorting complexity and leetcode task

There is an easy leetcode task:

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

And the function signature is 

public boolean isAnagram(String s, String t) {

}

At the first glance it could be solved with two algorithms.

The first algorithm:

1. convert input strings to char arrays

2. sort char arrays

3. compare arrays symbol-by-symbol, if they are not identical return false, otherwise we have valid anagram and must return true

Coplexity of the first algorithm equals to complexety of sorting char array which "offers O(n log(n)) performance" 

The second algorithm:

1. Iterate through all symbols of the 's' string and put each symbol to the map where key is the symbol itself and the value is the counter (if we met a symbol we need to increment the counter)

2. Iterate through all symbols of the 't' string and decrement the counter for each symbol in the map 

3. Iterate through all map values and check if counter equals '0' for every symbol (map key), it means that we got valid anagram

Complexity of the second algorithm equals to complexity of iterating through the arrays and symbol-counter map which is no more than O(n).

Looks like the second solution should work faster but leetcode checker engine doesn't think so...