17

I'm trying to make a function that returns the index of the Nth occurrence of a given char in a string.

Here is my attempt:

private int IndexOfNth(string str, char c, int n)
{
    int index = str.IndexOf(c) + 1;
    if (index >= 0)
    {
        string temp = str.Substring(index, str.Length - index);
        for (int j = 1; j < n; j++)
        {
            index = temp.IndexOf(c) + 1;
            if (index < 0)
            {
                return -1;
            }
            temp = temp.Substring(index, temp.Length - index);
        }
        index = index + (str.Length);
    }
    return index;
}

This should find the first occurrence, chop off that front part of the string, find the first occurrence from the new substring, and on and on until it gets the index of the nth occurrence. However I failed to consider how the index of the final substring is going to be offset from the original actual index in the original string. How do I make this work?

Also as a side question, if I want the char to be the tab character do I pass this function '\t' or what?

abatishchev
  • 98,240
  • 88
  • 296
  • 433
Kyle V.
  • 4,752
  • 9
  • 47
  • 81
  • 2
    possible duplicate of [Find Nth occurrence of a character in a string](http://stackoverflow.com/questions/2571716/find-nth-occurrence-of-a-character-in-a-string) – Eren Ersönmez Jul 06 '12 at 13:35
  • Hmm... I wonder if you can do `int f = 0; return str.TakeWhile(x => x != t || ++f < n).Count();`? – Ry- Jul 06 '12 at 13:39

9 Answers9

44

Don't do that; IndexOf takes a second parameter that specifies where to start.

private static int IndexOfNth(string str, char c, int n) {
    int s = -1;

    for (int i = 0; i < n; i++) {
        s = str.IndexOf(c, s + 1);

        if (s == -1) break;
    }

    return s;
}
Ry-
  • 218,210
  • 55
  • 464
  • 476
26

Taking all these substrings seems pretty wasteful to me. Why not just loop yourself?

private int IndexOfNth(string str, char c, int n)
{
    int remaining = n;
    for (int i = 0; i < str.Length; i++)
    {
        if (str[i] == c)
        {
            remaining--;
            if (remaining == 0)
            {
                return i;
            }
        }
    }
    return -1;
}

(I considered using IndexOf in a loop like minitech's solution, but decided it was a bit fiddly. Either's fine, of course. Both basically do the same work, only ever checking each character once. Using IndexOf may be slightly more efficient, but go for whichever you find more readable.)

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
14

Using LINQ to find the index of the 5'th a in the string aababaababa:

var str = "aababaababa";
var ch = 'a';
var n = 5;
var result = str
  .Select((c, i) => new { c, i })
  .Where(x => x.c == ch)
  .Skip(n - 1)
  .FirstOrDefault();
return result != null ? result.i : -1;
Martin Liversage
  • 104,481
  • 22
  • 209
  • 256
  • 1
    Not as efficient as the solutions that simply loops over the characters in the string. – Martin Liversage Jul 06 '12 at 13:40
  • I like this answer but in VS2010 I'm getting a red underline under `.Select` with text: `'System.Array' does not contain a definition for 'Select' and no extension method 'Select' accepting a first argument of type 'System.Array' could be found (are you missing a using directive or an assembly reference?)` – Kyle V. Jul 06 '12 at 13:44
  • @StickFigs: Make sure you've referenced and are `using` `System.Linq`. – Ry- Jul 06 '12 at 13:46
  • @MartinLiversage It's not just about efficiency but looking at a problem from different perspectives and you did a good job showing yours. –  Jul 06 '12 at 13:46
  • @StickFigs: You need to import the extension methods of the `System.Linq.Enumerable` class by adding by adding `using System.Linq` at the top of your source file. – Martin Liversage Jul 06 '12 at 13:46
  • Could you please explain this line to me: `return result != null ? result.i : -1;` – Kyle V. Jul 06 '12 at 13:51
  • 2
    @StickFigs: If there is no first item, `.FirstOrDefault()` returns `null`, so you can't get the `i` property (or is it a field with anonymous types?) and you want `-1`. – Ry- Jul 06 '12 at 13:54
  • 1
    Why do you need to use `ToCharArray` to copy the string into a new `char[]`? String is `IEnumerable` already. Is it more efficient? – Tim Schmelter Jul 06 '12 at 13:56
  • 1
    @StickFigs: I have also upvoted this answer, but it's rather a feasibility study than the _best_ way(imho). To be hoest minitechs or J.Skeets approaches are more efficient and even more readable. – Tim Schmelter Jul 06 '12 at 14:12
  • 2
    @TimSchmelter: I don't need to use `ToCharArray`. Thanks for pointing it out. – Martin Liversage Jul 06 '12 at 15:13
6

I tend to first think about how to access the collection using Linq.

  // 0-based n.
char result = str
  .Where(x => x == c)
  .Skip(n)
  .FirstOrDefault();

Then I'll unpack the linq and add the indexed iteration.

int foundCount = -1;
for(int position = 0; position < str.Length; position++)
{
  char x = str[position];
  if (x == c)
  {
    foundCount += 1;
    // 0-based n
    if (foundCount == n)
    {
      return position;
    }
  }
}
return -1;

Then I think about: what if this method returned all the indexes so I can query them:

public IEnumerable<int> IndexesOf(string str, char c)
{
  for(int position = 0; position < str.Length; position++)
  {
    char x = str[position];
    if (x == c)
    {
      yield return position;
    }
  }
}

Called by:

int position = IndexesOf(str, c)
 .Skip(n) // 0-based n
 .DefaultIfEmpty(-1)
 .First();
Amy B
  • 108,202
  • 21
  • 135
  • 185
  • +1, but here are some minor fixes in the call: `int position = Positions(str, ch).Skip(n-1).DefaultIfEmpty(-1).First();` – Tim Schmelter Jul 06 '12 at 14:30
  • @TimSchmelter thanks for the tip on DefaultIfEmpty - I should have checked my overloads. I'm going to stay with 0-based indexing on this Skip. – Amy B Jul 06 '12 at 14:46
1

Instead of creating a bunch of substrings, why not use the IndexOf overload that takes a starting index? This will be both easier (you won't have to adjust the final index) and more efficient (you don't have to allocate a bunch of substrings).

Dan Tao
  • 125,917
  • 54
  • 300
  • 447
1

Not tested but something like this should work:

private int IndexOfNth(string str, char c, int n)
{
    int index = -1;
    while (n-- > 0)
    {
        index = str.IndexOf(c, index + 1);
        if (index == -1) break;
    }
    return index;
}
Chris Snowden
  • 4,982
  • 1
  • 25
  • 34
0

Hadn't seen anyone use the CharEnumerator yet...

    public Int32 getNthIndex(string str, char c, Int32 n)
    {
        Int32 index = 0;
        Int32 count = 0;
        if (str != null && str.Length > 0 && !(n < 1))
        {
            CharEnumerator scanner = str.GetEnumerator();
            while (scanner.MoveNext())
            {
                if (scanner.Current == c) { count++; }
                if (count == n) { break; }
                index++;
            }
            if (count < n) { index = -1; }
        }
        if (count == 0) { return -1; } else { return index; }
    }

Should be pretty efficient, no substrings or anything, just scan through the string you're given and keep count.

Kevin
  • 704
  • 3
  • 4
  • Why would you use a `CharEnumerator` explicitly when a `foreach` loop already uses it implicitly? Also, your last paragraph is completely false. – Ry- Jul 07 '12 at 01:59
  • I dissagree about my last paragraph. All of the other solutions will return the index of the n - 1 occurance of c instead of correctly reporting -1 (indicating the nth occurance was not found) as mine does. – Kevin Jul 09 '12 at 12:53
  • Also, let me turn around your question to me. Why would you prefer the foreach loop abstraction which, in this case, does not buy you anything over directly using the CharEnumerator. I was mearly presenting a viable alternative which is what I thought constructive discourse was all about. – Kevin Jul 09 '12 at 13:53
  • Obviously you haven't actually tried all the other solutions. I haven't either, but I have tried mine (works) and Jon Skeet's (works), and through a cursory inspection it seems that *every* answer does that. As for the `foreach` loop abstraction, I would prefer it because it's shorter and much more obvious. You've managed to make C# look like Java. Also, despite all the checks that shouldn't really be there, your code still manages to return an incorrect result for `getNthIndex("a", 'a', 0)`: `1`, as opposed to `-1`. Fixed all that for you. https://gist.github.com/3076861 – Ry- Jul 09 '12 at 14:25
  • I appologize and concede that I had not tried the other solutions. Also that I have since tried your solution and it indeed works under the conditions that I had outlined, and that mine returned (incorectly) 1 under the input you defined (I have fixed this in the latest edit). I therefore retract my last paragraph (and have removed it). However, in regards to the "checks that shouldn't be there" try feeding your solution (null, 'a', 1) and see how well it fares. – Kevin Jul 09 '12 at 14:56
  • Hmm, you're right. Maybe something more appropriate would be to throw an `ArgumentNullException`? It might be neater: `if(str == null) throw new ArgumentNullException("str");` – Ry- Jul 09 '12 at 15:42
0

You could use the following method which will return the nth occurrence of the specified character within the designated string.

public static int IndexOfNthCharacter(string str, int n, char c) {
    int index = -1;
    if (!str.Contains(c.ToString()) || (str.Split(c).Length-1 < n)) {
        return -1;
    }
    else {
        for (int i = 0; i < str.Length; i++) {
            if (n > 0) {            
                index++;
            }
            else {
                return index;
            }
            if (str[i] == c) {
                n--;
            }
        }
        return index;
    }
}

Note that if the character you are searching for does not exist within the string you are searching or the the occurrence number you are searching for is greater than what exists in the string then this method will return -1.

FrostyOnion
  • 856
  • 7
  • 10
-1

First of all, I'd make it an extension method. This way, you can skip the otherwise obligatory null check and also just call it on a string like you would do with IndexOf, IndexOfAny etc.

Then I'd make two methods of this. One to retrieve all indexes (IndexesOf, that might come handy at sometime) and the other one (IndexOfNth) uses the first function to check for the nth index:

using System;
using System.Collections.Generic; // # Necessary for IList<int>
using System.Linq; // # Necessary for IList<int>.ToArray()

/// <summary>
/// Returns all indexes of the specified <paramref name="value"/> in the current string.
/// </summary>
/// <param name="@this">The current string this method is operating on.</param>
/// <param name="value">The value to be searched.</param>
/// <returns><c>Null</c>, if <paramref name="value"/> is <c>null</c> or empty.
/// An array holding all indexes of <paramref name="value"/> in this string,
/// else.</returns>
static int[] IndexesOf(this string @this, string value)
{
    // # Can't search for null or string.Empty, you can return what
    //   suits you best
    if (string.IsNullOrEmpty(value))
        return null;

    // # Using a list instead of an array saves us statements to resize the 
    //   array by ourselves
    IList<int> indexes = new List<int>();
    int startIndex = 0;

    while (startIndex < @this.Length)
    {
        startIndex = @this.IndexOf(value, startIndex);
        if (startIndex >= 0)
        {
            // # Add the found index to the result and increment it by length of value
            //   afterwards to keep searching AFTER the current position
            indexes.Add(startIndex);
            startIndex += value.Length;
        }
        else
        {
            // # Exit loop, if value does not occur in the remaining string
            break;
        }
    }

    // # Return an array to conform with other string operations.
    return indexes.ToArray();
}

/// <summary>
/// Returns the indexes of the <paramref name="n"/>th occurrence of the specified
/// <paramref name="value"/> in the current string.
/// </summary>
/// <param name="@this">The current string this method is operating on.</param>
/// <param name="value">The value to be searched.</param>
/// <param name="n">The 1-based nth occurrence.</param>
/// <returns><c>-1</c>, if <paramref name="value"/> is <c>null</c> or empty -or-
/// <paramref name="n"/> is less than 1.</returns>
static int IndexOfNth(this string @this, string value, int n /* n is 1-based */)
{
    // # You could throw an ArgumentException as well, if n is less than 1
    if (string.IsNullOrEmpty(value) || n < 1)
        return -1;

    int[] indexes = @this.IndexesOf(value);

    // # If there are n or more occurrences of 'value' in '@this'
    //   return the nth index.
    if (indexes != null && indexes.Length >= n)
    {
        return indexes[n - 1];
    }

    return -1;
}

You can overload these using char value instead of string value in the signature and calling their respective counterparts passing value.ToString(). Et voilá!

Surely, these methods can be refactored, e.g. using LINQ, make IndexesOf recursive etc.

Tim
  • 157
  • 1
  • 11