5
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ input missing null validation. n missing negative integers && 0 validation. \$\endgroup\$
    – iSR5
    Aug 20, 2020 at 2:47

4 Answers 4

4
\$\begingroup\$
  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
  1. 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
  1. 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.

  1. 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;
  1. 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'));
\$\endgroup\$
1
  • \$\begingroup\$ Thank you for your comment. I like chaining link expressions but I split them up for readability. It should also be noted that this code was fed to a parser/compiler on the hackerrank.com website that must be able to parse and compile it. \$\endgroup\$ Sep 2, 2020 at 13:37
3
\$\begingroup\$

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'));
}
\$\endgroup\$
2
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for your comment. I like the idea of using loops. I did try using loops. Unfortunately use of loops caused a literal stack overflow. I think the second test case is designed to break loop-based solutions. \$\endgroup\$ Sep 2, 2020 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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