Nth Index of Char in String

Question

I've written a function that searches for the nth occurrence of a character in the given string. A positive value for n will search from left-to-right, while a negative value will search from right-to-left. Zero is not a valid value for n.

Left-to-Right Search

"AABAXYAMN".NthIndexOf('A', 1) -> 0
"AABAXYAMN".NthIndexOf('A', 2) -> 1
"AABAXYAMN".NthIndexOf('A', 3) -> 3

Right-to-Left Search

"AABAXYAMN".NthIndexOf('A', -1) -> 6
"AABAXYAMN".NthIndexOf('A', -2) -> 3
"AABAXYAMN".NthIndexOf('A', -3) -> 1

Code:

/// <summary>
/// Searches for the nth occurrence of a character in the given string. A positive value for n will search from
/// left-to-right while a negative value will search from right-to-left. Zero is not a valid value for n.
/// </summary>
public static int NthIndexOf(this string input, char charToFind, int n) {
    int position;

    switch (Math.Sign(n)) {
        case 1:
            position = 0;
            while (((position = input.IndexOf(charToFind, position)) != -1) && ((--n) > 0)) { position++; }
            break;
        case -1:
            position = input.Length - 1;
            while (((position = input.LastIndexOf(charToFind, position)) != -1) && ((++n) < 0)) { position--; }
            break;
        default:
            throw new ArgumentOutOfRangeException(message: "param cannot be equal to 0", paramName: nameof(n));
    }

    return position;
}

Answer 1

First, your loops are evil to read. It took me several minutes to figure out what the condition did. Essentially, you loop N times, where N is the Nth instance of the character in the string you wish to find the index for. Each time you loop, you find the index of the next occurrence of the character in the string, update the position to search from, and continue the process until the index is either -1 (no Nth instance), or until n > 0 or n < 0, based on which side you are searching from.

A simpler way to write this algorithm is as follows:

public static int NthIndexOfC(this string input, char charToFind, int n)
{
    int position;

    switch (Math.Sign(n))
    {
        case 1:
            position = -1;
            do
            {
                position = input.IndexOf(charToFind, position + 1);
                --n;
            } while (position != -1 && n > 0);
            break;
        case -1:
            position = input.Length;
            do
            {
                position = input.LastIndexOf(charToFind, position - 1);
                ++n;
            } while (position != -1 && n < 0);
            break;
        default:
            throw new ArgumentOutOfRangeException(message: "param cannot be equal to 0", paramName: nameof(n));
    }

    return position;
}

It takes a little bit more room since I wrote the loop body on its own lines, but it is easy to understand, and there are no assignments in the loop condition.

However, this is still not the way I would write this algorithm. When you think about how IndexOf works, it iterates the string with a for loop from the specified starting index until it reaches the first instance of the requested character, which it returns. We can write similar behavior, but just keep track of which index we are at:

public static int NthIndexOf(this string input, char charToFind, int n)
{
    int count = 0;
    switch (Math.Sign(n))
    {
        case 1:
            for (var index = 0; index < input.Length; index++)
            {
                if (input[index] == charToFind)
                {
                    count++;
                }

                if (count == n)
                {
                    return index;
                }
            }
            break;
        case -1:
            for (var index = input.Length - 1; index >= 0; index--)
            {
                if (input[index] == charToFind)
                {
                    count++;
                }

                if (count == Math.Abs(n))
                {
                    return index;
                }
            }
            break;
        default:
            throw new ArgumentOutOfRangeException(message: "param cannot be equal to 0", paramName: nameof(n));
    }

    return -1;
}

This is the longest solution yet, but we aren't finished. Notice all that duplicated code?

public static int NthIndexOf(this string input, char charToFind, int n)
{
    switch (Math.Sign(n))
    {
        case 1:
            return NthIndexOf(input, charToFind, n, 0, input.Length);
        case -1:
            return NthIndexOf(input, charToFind, n, input.Length - 1, -1);
        default:
            throw new ArgumentOutOfRangeException(message: "param cannot be equal to 0", paramName: nameof(n));
    }
}

public static int NthIndexOf(string input, char charToFind, int n, int searchFrom, int searchTo)
{
    int count = 0;
    var index = searchFrom;

    while (index != searchTo)
    {
        if (input[index] == charToFind)
        {
            count++;
        }

        if (count == Math.Abs(n))
        {
            return index;
        }

        index += Math.Sign(n);
    }

    return -1;
}

There. Clean, easy to understand and maintain, and lots of options to use. Notice that the second NthIndexOf needs to have the searchTo one integer larger or smaller than the value you want to stop at to accommodate the multi-directional search.

Answer 2

I don't think this method is very useful. It does simply too much. Make it the LINQ way and separate the logic into multiple methods.

Create two methods that search for the value and return an IEnumerable<int>:

public static IEnumerable<int> IndiciesOf(this string input, char value, int? startAt = null)
{
    startAt = startAt ?? 0;
    for (int i = startAt.Value; i < input.Length; i++)
    {
        if (input[i] == value)
        {
            yield return i;
        }
    }
}

public static IEnumerable<int> IndiciesOfReverse(this string input, char value, int? startAt = null)
{
    startAt = startAt ?? input.Length;
    for (int i = startAt.Value - 1; i >= 0; i--)
    {
        if (input[i] == value)
        {
            yield return i;
        }
    }
}

You could already use them in multiple scenarios. But let's go one step further and encapsulate your logic in two more extensions:

public static int NthIndexOf(this string input, char value, int n, int? startAt = null)
{
    return input
        .IndiciesOf(value, startAt)
        .Skip(n - 1)
        .DefaultIfEmpty(-1)
        .First();
}

public static int NthIndexOfReverse(this string input, char value, int n, int? startAt = null)
{
    return input
        .IndiciesOfReverse(value, startAt)
        .Skip(n - 1)
        .DefaultIfEmpty(-1)
        .First();
}

Or if you want to have only one method then try this (but make the other two private and add the suffix Internal - otherwise there'll be a conflict)

public static int NthIndexOf(this string input, char value, int n, int? startAt = null)
{
    return
        n >= 0
        ? input.NthIndexOf(value, n, startAt);
        : input.NthIndexOfReverse(value, n, startAt);
}

Answer 3

Pretty sure iterate the string once and add occurrence is more efficient than multiple calls to input.IndexOf. It has to skip forward by position multiple times.

For me it is also easier to read.

public int GetPosByCount(string s, char target, int n)
{
    if (String.IsNullOrEmpty(s))
        return -1;
    if (n > s.Length)
        return -1;
    if (n > 0)
    {
        int occurance = 0;
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == target)
            {                      
                if (occurance == n-1)
                    return i;
                occurance++;
            }
        }
        return -1;
    }
    else if (n < 0)
    {
        int occurance = 0;
        for (int i = s.Length - 1; i >= 0; i--)
        {
            if (s[i] == target)
            {
                if (occurance == n+1)
                    return i;
                occurance--;
            }
        }
        return -1;
    }
    else
    {
        return -1;
    }
}

Answer 4

By taking advantage of the Math.Sign operation and avoiding the use of IndexOf and LastIndexOf (as suggested by the great answers provided so far) I have come up with a version that avoids having two different algorithms.

I was really thrilled by the elegance of the answer given by @t3chb0t but, unfortunately, the state machine turns out to be roughly 5x slower even when I replace the LINQ calls with more efficient code. I also loved the thoroughness of the response by @Hosch250 as it gave me the idea that I could collapse the two algorithms into one and a solid foundation to work with.

There are some gymnastics being performed in the variable assignment in order to handle the loop direction and startIndex but other than that this feels far less "evil" than the original and it performs twice as fast to boot!

/// <summary>
/// Searches for the nth occurrence of a character in the given string. A positive value for n will search from
/// left-to-right while a negative value will search from right-to-left. Zero is not a valid value for n.
/// </summary>
public static int NthIndexOf(this string input, char charToFind, int n, int? startIndex = null) {
    if (startIndex < 0) { throw new ArgumentOutOfRangeException(message: "param cannot be less than 0", paramName: nameof(startIndex)); }

    var nSign = Math.Sign(n);
    var inputLength = ((input == null) ? 0 : input.Length);
    int index;
    int count;

    if (nSign == 1) {
        index = (startIndex ?? 0);
        count = (inputLength - index);
    }
    else if (nSign == -1) {
        index = (startIndex ?? (inputLength - 1));
        count = (index + 1);
    }
    else {
        throw new ArgumentOutOfRangeException(message: "param cannot be equal to 0", paramName: nameof(n));
    }

    while (count-- > 0) {
        if ((input[index] == charToFind) && ((n -= nSign) == 0)) {
            return index;
        }

        index += nSign;
    }

    return -1;
}

Answer 5

I know this is old, but this answer is the easiest.

You can use the extension function "AllIndexesOf" to get a list of indexes then you can grab the one you want:

List<int> indexes = "AAAXXXYYY".AllIndexesOf("A");
indexes.ElementAt(2);