C#: Repeated String

Question

From HackerRank "Repeated String" challenge:

Lilah has a string, \$s\$, of lowercase English letters that she repeated infinitely many times.

Given an integer, \$n\$, find and print the number of letter a's in the first \$n\$ letters of Lilah's infinite string.

For example, if the string \$s=abcac\$ and \$n=10\$, the sub string we consider is \$abcacabcac\$, the first \$10\$ characters of her infinite string. There are \$4\$ occurrences of a in the sub-string.

Test case 1:

        string input = "aba";
        long n = 10;

Test case 2:

        string input = "a";
        long n = 1000000000000;

My Solution:

        string input = "aba";
        long n = 10;
        long numAs = input.Count(c => c.Equals('a'));

        if (input.Length == 0)
        {
            return 0;
        }

        long rem = n % input.Length;
        long reps = (n - rem) / input.Length;
        long count = reps * numAs;

        string sRem = input.Substring(0, (int)rem);

        if (rem != 0)
        {
            count += sRem.Count(c => c.Equals('a'));
        }

The results should be 7 and 1000000000000. This solution passed all test cases on HackerRank. It is based on other solutions, especially one I up-voted.

Answer 1

1. Do you need to validate inputs ?

If so, you should test all cases :

• input could be null
• input could be an empty string
• n could be negative or 0

2. Variable names

Variables names are important, they help understand the code better. You don't have to make them as small as possible. Especially when you have an IDE like VisualStudio that will help you select the proper one with InteliSense.

• numAs -> aCount
• rem -> remainder
• reps -> repetitions
• sRem -> remainderString

3. Fail fast

It is usually better to leave a method "as soon as possible". So you want to perform input validation before doing any work and exit the method if it doesn't validate. The same way, if your remainder is 0, you can return your result right away.

4. Integer division

To calculate your repetition, you subtract the remainder from n. If you check integer division in C#, you don't have to :

long repetitions = n / input.length;

5. Use Linq

As per tinstaafl solution, you can use Linq to save a variable and a line :

count += remainderString.Take((int)remainder).Count(c => c.Equals('a'));

So, all in all, you get :

long aCount = input.Count(c => c.Equals('a'));

if (input == null || input.Length == 0 || n <= 0)
{
    return 0;
}

long repetitions = n / input.Length;
long remainder = n % input.Length;
long count = repetitions * aCount;

if (remainder == 0)
{
    return count;
}

return count + remainderString.Take((int)remainder).Count(c => c.Equals('a'));

Answer 2

I don't see a lot to improve. However, I did notice a couple of things:

The shortcut conditional:

if (input.Length == 0)
{
    return 0;
}

should be the very first thing in your code right after input

Similarly with:

string sRem = input.Substring(0, (int)rem);

if (rem != 0)
{
    count += sRem.Count(c => c.Equals('a'));
}

You don't need that string unless rem > 0, so include it in the conditional block. Even better yet, use the LINQ extension, Take and do everything in one statement:

if (rem != 0)
{
    count += sRem.Take((int)rem).Count(c => c.Equals('a'));
}

Answer 3

Same points as other answers, however there is a simpler solution to this, you can simply replace A with empty string, and compare the length of both strings, which would give you the number of A's.

Here is an example :

public static long RepeatedString(string s, long n)
{
    if (string.IsNullOrWhiteSpace(s) || n <= 0) { return 0; }
    
    // Local function that would return the number of A's 
    long CountA(string input) => input.Length - input.Replace("a", "").Length;
    
    var aCount = CountA(s);
    
    var reminder = n % s.Length; 
    
    var repetition = (n - reminder) / s.Length;
    
    var count = repetition * aCount;

    var reminderStr = s.Substring(0, (int)reminder);
    
    var result = count + CountA(reminderStr);
    
    return result;
}

Answer 4

I can't add much to what have already been written, other than when it comes to performance, you'll often find Linq (long numAs = input.Count(c => c.Equals('a'));) to be rather slow compared to a more traditional for or while loop. But if you insists on Linq, you could go all in like:

long CountChars(string data, long length, char c = 'a')
{
  if (string.IsNullOrEmpty(data) || length <= 0) return 0;

  long repetitions = length / data.Length;
  long remSize = length % data.Length;

  return data
    .Select((ch, i) => (ch, i))
    .Where(chi => chi.ch == c)
    .Sum(chi => chi.i < remSize ? repetitions + 1 : repetitions);
}

Here is used the overload of Select() that provides the index along with each element to map to a value tuple, from which it is possible to filter by 'a' and finally sums up the repetitions: if the index is lesser than the size of the reminder then repetitions + 1 should be summed otherwise only the repetitions for each found 'a'.

---

A traditional approach using while-loops - essentially using the same approach as above could look like:

long CountChars(string data, long length, char c = 'a')
{
  if (string.IsNullOrEmpty(data) || length <= 0) return 0;

  long count = 0;
  long repetitions = length / data.Length + 1; // + 1 for the possible extra 'a' in the reminder
  long remSize = length % data.Length;

  int i = 0;

  while (i < remSize)
  {
    if (data[i++] == c)
      count += repetitions;
  }

  repetitions--;
  while (i < data.Length)
  {
    if (data[i++] == c)
      count += repetitions;
  }

  return count;
}

With this approach the string s (data) is only parsed once.