locked
How to find the nth occurrence of a character in a given string?

    Question

  • Hi All,
    I have a string and I need to find the index of third occurrence of a given character. I could easily find the first and last occurrences
    I could do this by writing a for loop and checking each and every character, bu is there any other way?

    Thanks
    Regards

    Regards Sridhar
    Thursday, April 02, 2009 11:11 AM

Answers

  • You'd think the best way would be to use IndexOf(), but in fact in release mode (but not debug mode) looping yourself is quicker!

    In my test code below, looping took 0.27s while using IndexOf() took 0.36s:

    using System;
    using System.Diagnostics;
    
    namespace ConsoleApplication1
    {
        static class Program
        {
            static void Main()
            {
                string s = "l;sdhjkjhsvhehevjhkjeokjkakfl;kjavkl;lkalkllkvlkalkle;kljaekljndfvnuvuiwel;kja;vlkjajvdsfg";
                int occurance = 8;
                int count = 1000000;
                char c = 'v';
    
                Stopwatch sw = new Stopwatch();
                sw.Start();
    
                for (int i = 0; i < count; ++i)
                {
                    IndexOfNthOccuranceMethodOne(s, c, occurance);
                }
    
                sw.Stop();
                Console.WriteLine("Method one took " + sw.Elapsed);
                sw.Reset();
                sw.Start();
    
                for (int i = 0; i < count; ++i)
                {
                    IndexOfNthOccuranceMethodTwo(s, c, occurance);
                }
    
                sw.Stop();
                Console.WriteLine("Method two took " + sw.Elapsed);
            }
    
            static int IndexOfNthOccuranceMethodOne(string s, char c, int occurance)
            {
                for (int i = 0, count = 0; i < s.Length; ++i)
                {
                    if (s[i] == c)
                    {
                        if (++count == occurance)
                        {
                            return i;
                        }
                    }
                }
    
                return -1;
            }
    
            static int IndexOfNthOccuranceMethodTwo(string s, char c, int occurance)
            {
                int index = -1;
                int found = 0;
    
                while (true)
                {
                    index = s.IndexOf(c, index+1);
    
                    if (index < 0)
                    {
                        return -1;
                    }
    
                    if (++found == occurance)
                    {
                        return index;
                    }
                }
            }
        }
    }
    • Proposed as answer by Matthew Watson Thursday, April 02, 2009 1:11 PM
    • Marked as answer by Harry Zhu Tuesday, April 07, 2009 7:36 AM
    Thursday, April 02, 2009 1:11 PM

All replies

  • string s = "aakhfsadjkfhasjdkfhksdf";
                int count = 3;
                int i = 0;
                int index;
                while (i < count)
                {
                    index = s.IndexOf('a');
                    s = s.Substring(index+1);
                    i++;
                }
    Thanks, A.m.a.L | [Remember to click "mark as answered" when you get a correct reply to your question]
    Thursday, April 02, 2009 11:34 AM
  • You'd think the best way would be to use IndexOf(), but in fact in release mode (but not debug mode) looping yourself is quicker!

    In my test code below, looping took 0.27s while using IndexOf() took 0.36s:

    using System;
    using System.Diagnostics;
    
    namespace ConsoleApplication1
    {
        static class Program
        {
            static void Main()
            {
                string s = "l;sdhjkjhsvhehevjhkjeokjkakfl;kjavkl;lkalkllkvlkalkle;kljaekljndfvnuvuiwel;kja;vlkjajvdsfg";
                int occurance = 8;
                int count = 1000000;
                char c = 'v';
    
                Stopwatch sw = new Stopwatch();
                sw.Start();
    
                for (int i = 0; i < count; ++i)
                {
                    IndexOfNthOccuranceMethodOne(s, c, occurance);
                }
    
                sw.Stop();
                Console.WriteLine("Method one took " + sw.Elapsed);
                sw.Reset();
                sw.Start();
    
                for (int i = 0; i < count; ++i)
                {
                    IndexOfNthOccuranceMethodTwo(s, c, occurance);
                }
    
                sw.Stop();
                Console.WriteLine("Method two took " + sw.Elapsed);
            }
    
            static int IndexOfNthOccuranceMethodOne(string s, char c, int occurance)
            {
                for (int i = 0, count = 0; i < s.Length; ++i)
                {
                    if (s[i] == c)
                    {
                        if (++count == occurance)
                        {
                            return i;
                        }
                    }
                }
    
                return -1;
            }
    
            static int IndexOfNthOccuranceMethodTwo(string s, char c, int occurance)
            {
                int index = -1;
                int found = 0;
    
                while (true)
                {
                    index = s.IndexOf(c, index+1);
    
                    if (index < 0)
                    {
                        return -1;
                    }
    
                    if (++found == occurance)
                    {
                        return index;
                    }
                }
            }
        }
    }
    • Proposed as answer by Matthew Watson Thursday, April 02, 2009 1:11 PM
    • Marked as answer by Harry Zhu Tuesday, April 07, 2009 7:36 AM
    Thursday, April 02, 2009 1:11 PM
  • It turns out that this method is very slightly faster still:

    static int IndexOfNthOccuranceMethodThree(string s, char c, int occurance)
    {
        int i = 0;
        int count = 0;
    
        foreach (char ch in s)
        {
            if (ch == c)
            {
                if (++count == occurance)
                {
                    return i;
                }
            }
    
            ++i;
        }
    
        return -1;
    }
    

    Thursday, April 02, 2009 1:20 PM
  •             string str = "aaa";

     

                var index = str.IndexOf("a");

                for (int i = 0; i < 2; i++)

                {

                    index = str.IndexOf("a", i + 1);

                }

     

                MessageBox.Show(index.ToString());

    Thursday, April 02, 2009 6:54 PM
  • Mathew can you time this:

    static int IndexOfNthOccuranceMethodThree(string s, char c, int occurance)
    {
    	var pair = ((IEnumerable<char>)s)
    		.Select((ch, i) => new { character = ch, index = i })
    		.Where(p => p.character == c)
    		.Skip(occurance - 1)
    		.FirstOrDefault();
    
    	if (pair == null)
    		return -1;
    	else
    		return pair.index;
    }
    
    

    Edit: Forget about it. I just timed it and it sucks. :D
    Thursday, April 02, 2009 7:13 PM
  • Linq is almost always slower than other methods.  It's made for convenience, not performance.  My tests had the following results with Linq:

    Method one took 00:00:01.7154266
    Method two took 00:00:00.6869571
    Method three took 00:00:16.2309634
    David Morton - http://blog.davemorton.net/
    Thursday, April 02, 2009 7:40 PM
    Moderator