C#: String Repetida

Question

Do desafio "Sequência repetida" do HackerRank:

Lilah tem uma string, \$s\$, de letras minúsculas do inglês que ela repetia infinitas vezes.

Dado um inteiro, \$n\$, localize e imprima o número de letras a no primeiro \$n\$letras da corda infinita de Lilah.

Por exemplo, se a string \$s=abcac\$e \$n=10\$, a substring que consideramos é \$abcacabcac\$, o primeiro \$10\$caracteres de sua cadeia infinita. Existem \$4\$ocorrências de a na substring.

Caso de teste 1:

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

Caso de teste 2:

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

Minha solução:

        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'));
        }

Os resultados devem ser 7 e 1000000000000. Esta solução passou em todos os casos de teste no HackerRank. É baseado em outras soluções, especialmente uma que eu votei.

Answer 1

1. Você precisa validar as entradas?

Se assim for, você deve testar todos os casos:

• a entrada pode ser nula
• a entrada pode ser uma string vazia
• n pode ser negativo ou 0

1. nomes de variáveis

Os nomes das variáveis ​​são importantes, pois ajudam a entender melhor o código. Você não precisa torná-los tão pequenos quanto possível. Especialmente quando você tem um IDE como o VisualStudio, que o ajudará a selecionar o adequado com o InteliSense.

• numAs -> aContagem
• rem -> restante
• repetições -> repetições
• sRem -> restoString

1. Falha rápido

Geralmente é melhor deixar um método "o mais rápido possível". Portanto, você deseja executar a validação de entrada antes de fazer qualquer trabalho e sair do método se ele não for validado. Da mesma forma, se o resto for 0, você pode retornar o resultado imediatamente.

1. divisão inteira

Para calcular sua repetição, você subtrai o restante de n. Se você verificar a divisão inteira em C# , não precisará:

long repetitions = n / input.length;

1. Usar Linq

De acordo com a solução tinstaafl , você pode usar o Linq para salvar uma variável e uma linha:

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

Então, ao todo, você obtém:

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

Não vejo muito o que melhorar. No entanto, notei algumas coisas:

A condicional de atalho:

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

deve ser a primeira coisa em seu código logo apósinput

Da mesma forma com:

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

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

Você não precisa dessa string a menos que rem> 0, então inclua-a no bloco condicional. Melhor ainda, use a extensão LINQ Takee faça tudo em uma instrução:

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

Answer 3

Mesmos pontos que outras respostas, no entanto, há uma solução mais simples para isso, você pode simplesmente substituir Apor string vazia e comparar o comprimento de ambas as strings, o que lhe daria o número de A's.

Aqui está um exemplo :

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

Não posso acrescentar muito ao que já foi escrito, exceto quando se trata de desempenho, você frequentemente achará o Linq ( long numAs = input.Count(c => c.Equals('a'));) bastante lento em comparação com um loop forou whileloop mais tradicional. Mas se você insiste em Linq, você pode ir all-in como:

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);
}

Aqui é usada a sobrecarga de Select()que fornece o índice junto com cada elemento para mapear para uma tupla de valor, a partir da qual é possível filtrar 'a'e finalmente somar as repetições: se o índice for menor que o tamanho do lembrete, então repetitions + 1deve ser somado de outra forma apenas as repetições para cada encontrado 'a'.

---

Uma abordagem tradicional usando while-loops - essencialmente usando a mesma abordagem acima pode ser semelhante a:

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;
}

Com essa abordagem, a string s( data) é analisada apenas uma vez.