Runs in O(N) unless N < 256, in which case O(1).

Sorry, this is C#, but the same idea should work in Java.

    public bool SameCharacters(string string1, string string2)
    {
        var encoding = System.Text.ASCIIEncoding.ASCII;

        Byte[] bytes1 = encoding.GetBytes(string1);
        Byte[] bytes2 = encoding.GetBytes(string2);

        if (string1.Length != string2.Length) return false;

        int[] counts = new int[256];
        for (int i = 0; i < string1.Length; i++)
        {
            counts[bytes1[i]]++;
            counts[bytes2[i]]--;
        }

        foreach (var count in counts)
        {
            if (count != 0) return false;
        }

        return true;
    }

This just takes advantage of the fact that each character has a numeric value. If you wanted to consider more than just ascii, you could replace the count array with a map from int -> int and use a different encoding.

Runs in O(N).

Sorry, this is C#, but the same idea should work in Java.

    public bool SameCharacters(string string1, string string2)
    {
        var encoding = System.Text.ASCIIEncoding.ASCII;

        Byte[] bytes1 = encoding.GetBytes(string1);
        Byte[] bytes2 = encoding.GetBytes(string2);

        if (string1.Length != string2.Length) return false;

        int[] counts = new int[256];
        for (int i = 0; i < string1.Length; i++)
        {
            counts[bytes1[i]]++;
            counts[bytes2[i]]--;
        }

        foreach (var count in counts)
        {
            if (count != 0) return false;
        }

        return true;
    }

This just takes advantage of the fact that each character has a numeric value. If you wanted to consider more than just ascii, you could replace the count array with a map from int -> int and use a different encoding.