2

This is a very simple function to find if a string is composed of unique characters. I believe that this is a O(n) time complexity as it loops once and has a single if condition. Am I correct? Is there any way it can be optimized further?

public class Program
 {
    public static void Main(string[] args)
    {
        DuplicateChars(args[0].ToLower());
    }

    public static bool DuplicateChars(string str)
    {
        bool[] charfound = new bool[26];
        int index = 0;

        for(int i = 0; i <= str.Length ; ++i)
        {
            index = (byte)(str[i]);
            //subtract by ascii value of small a 97.
            index -= 97;
            if(charfound[index])
                return true;
            else
                charfound[index] = true;
        }  

        return false;
    }
}
  • 2
    str.ToLower is O(N) anyway – Caleth Dec 1 '16 at 12:58
  • @Caleth . Thanks. I made a change to remove ToLower() and move it to the calling function. I am only looking at the time complexity of DuplicateChars function. – Pradeep Loganathan Dec 1 '16 at 13:02
  • 3
    It will access the arraycharfound out of bounds if the string has non-alhpa chars. – qwerty_so Dec 1 '16 at 13:19
  • @ThomasKilian Thanks. One of assumptions is the we are passing characters in the alphabet (ascii range of 65 to 97 ) – Pradeep Loganathan Dec 1 '16 at 13:33
  • 1
    see What is O(…) and how do I calculate it? – gnat Dec 1 '16 at 13:34
5

Given your sample code I take it that the following assumption is true:

  • str only contains character values from 'a' to 'z'

Given that, we can immediately see an optimization opportunity: if str.Length is greater than charfound.Length, there will be a duplicated char, so we can include a check for that at the beginning of the function.

public class Program
{
    public static void Main(string[] args)
    {
        DuplicateChars(args[0].ToLower());
    }

    public static bool DuplicateChars(string str)
    {
        bool[] charfound = new bool[26];
        int index = 0;

        if(str.Length > charfound.Length) return true;

        for(int i = 0; i <= str.Length ; ++i)
        {
            index = (byte)(str[i]);
            //subtract by ascii value of small a 97.
            index -= 97;
            if(charfound[index])
                return true;
            else
                charfound[index] = true;
        }  

        return false;
    }
}

After this change, the worst case input would be a string consisting of a permutation of "abcdefghijklmnopqrstuvwxyz", which would mean that the function is O(1) in the worst case. (Proof of this is left as an exercise for the reader.)

EDIT: As pointed out by @Pieter B in the comments, you'd probably want to move the call to ToLower() from Main to right after the line if(str.Length > charfound.Length) return true; so you don't spend O(n) time in total.

  • Either you accept your algorithm handles 'a' and 'A' as separate letters (which may or may not be a bug), or args[0].ToLower() should be part of the algorithm, which makes it O(n) – Vincent Savard Dec 1 '16 at 13:42
  • .ToLower should be called after the length check. But for the rest I like this answer and the explanation. – Pieter B Dec 1 '16 at 13:43
  • @PieterB That would make more sense indeed. – Vincent Savard Dec 1 '16 at 13:43
  • 1
    @PieterB: well, it's only O(1) because of the optimization based on my assumption on the input alphabet, which could possibly be wrong, so I'd rather be careful before I make a too general statement, since his original code was O(n). (I guess the assumption was correct since my answer got accepted, but still...) – hoffmale Dec 1 '16 at 13:44
  • @Vincent: how you get a valid input sequence for this function is up to you (i.e. the call of args[0].ToLower() is outside of the scope of the given question). That said, you could move it back in, but that changes the contract of DuplicateChars, since strcan now contain chars in the range [a-zA-Z]. – hoffmale Dec 1 '16 at 13:47
2

You can improve it if you have extra information about the size of your alphabet.

Let's assume your string can ONLY have ASCII characters. That means that you can have at most 128 unique characters in your string. Any string with more than 128 characters will have duplicate characters.

What that means is that you only have to execute DuplicateChars if the string length is smaller or equal to 128, which places a constant upper bound on n and makes the algorithm O(1).

-1

Still O(n) but a lot less code

public static bool StringHasDup(string s)
{
    return (s.Length != new HashSet<char>(s.ToCharArray()).Count);
}
  • The accepted answer is O(1). And I think your version will be slower than OP's. (I didn't downvote though). – RemcoGerlich Dec 6 '16 at 13:23
  • @RemcoGerlich I bet it will beat the OP in speed and can add s.Length > statement. – paparazzo Dec 6 '16 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.