Encontrar a substring de tamanho k com o maior número de vogais

[mabranches]

Uma função find_substr recebe uma string e um inteiro k. Deve retornar a substring de tamanho k com o maior numero de vogais.
Se 2 iguais existirem deve retornar a que aparece primeiro:
Exemplo
caberqiitefg 5 -> erqii

[mabranches]

Solução lenta Ruby O(N*K)

VOWELS={
  a: 1,
  e: 1,
  i: 1,
  o: 1,
  u: 1
}
​
def count_vowels(s)
  count = 0
  for c in s.each_char
    count +=1 if VOWELS[c.to_sym]
  end
  count
end
​
#O (N * K)
def find_substring(s, k)
  return s if s.length <= k
​
  vow_count = count_vowels(s[0..k])
  vow_str = s[0..k-1]
  (1..s.length-k-1).each do |i|
    new_str = s[i..i+k-1]
    new_count = count_vowels(new_str)
    if (new_count > vow_count)
      vow_count = new_count
      vow_str = new_str
    end
  end
​
  vow_str
end
​
puts find_substring('caberqiitefg', 5)
puts find_substring('caberqjalskjdalskjdalskjdalskjdalsjdalsjdiueoriejwn,dhuyeqooidsqwmliausaspçqlwkeiitefg', 12)

[mabranches]

Solução rápida Ruby O(N)

VOWELS={
  a: 1,
  e: 1,
  i: 1,
  o: 1,
  u: 1
}
​
def count_vowels(s)
  count = 0
  for c in s.each_char
    count +=1 if VOWELS[c.to_sym]
  end
  count
end
​
​
#O (N)
def find_substring(s, k)
  return s if s.length <= k
​
​
  vow_str = s[0..k-1]
  vow_count = count_vowels(vow_str)
  curr_count = vow_count
  (1..s.length-k-1).each do |i|
    curr_count -= 1 if VOWELS[s[i-1].to_sym]
    curr_count += 1 if VOWELS[s[i + k - 1].to_sym]
    curr_str = s[i..i+k-1]
    if (curr_count > vow_count)
      vow_count = curr_count
      vow_str = curr_str
    end
  end
​
  vow_str
end
​
​
puts find_substring('caberqiitefg', 5)
puts find_substring('caberqjalskjdalskjdalskjdalskjdalsjdalsjdiueoriejwn,dhuyeqooidsqwmliausaspçqlwkeiitefg', 12)

[mabranches]

Solução Java

import java.util.Map;
​
public class Vowels {
​
    private final String s;
    private final int k;
​
    public Vowels(final String s, final int k) {
        this.s = s;
        this.k = k;
    }
​
    private final static Map<Character, Boolean> VOWELS = Map.of(
            'a', true,
            'e', true,
            'i', true,
            'o', true,
            'u', true
    );
​
​
    public static void main(String[] args) {
        System.out.println(new Vowels("caberqiitefg", 5).findSubstringSlow());
        System.out.println(new Vowels("caberqjalskjdalskjdalskjdalskjdalsjdalsjdiueoriejwn,dhuyeqooidsqwmliausaspçqlwkeiitefg", 12).findSubstringSlow());
        System.out.println(new Vowels("caberqiitefg", 5).findSubstring());
        System.out.println(new Vowels("caberqjalskjdalskjdalskjdalskjdalsjdalsjdiueoriejwn,dhuyeqooidsqwmliausaspçqlwkeiitefg", 12).findSubstring());
    }
​
    private String findSubstringSlow(){
        if (s.length() <= k){
            return s;
        }
​
        String vowStr = s.substring(0,k-1);
        int vowCount = countVowels(vowStr);
​
        for (int i = 1; i < s.length() - k; i ++){
            String newStr = s.substring(i, i + k - 1);
            int newCount = countVowels(newStr);
            if (newCount > vowCount){
                vowCount = newCount;
                vowStr = newStr;
            }
        }
        return vowStr;
    }
​
    private String findSubstring(){
        if (s.length() <= k){
            return s;
        }
​
        String vowStr = s.substring(0,k-1);
        int vowCount = countVowels(vowStr);
        int currCount = vowCount;
​
        for (int i = 1; i < s.length() - k; i ++){
            //curr_count -= 1 if VOWELS[s[i-1].to_sym]
​
            if (VOWELS.get(s.charAt(i - 1)) != null){
                currCount--;
            }
​
            if (VOWELS.get(s.charAt(i + k - 1)) != null){
                currCount++;
            }
​
            String currStr = s.substring(i, i + k - 1);
​
            if (currCount > vowCount){
                vowCount = currCount;
                vowStr = currStr;
            }
        }
        return vowStr;
    }
​
    private int countVowels(String s){
        int count = 0;
        for (char c : s.toCharArray()) {
            if (VOWELS.get(c) != null){
                count++;
            }
        }
        return count;
    }
}

[leofachetti]

Solução Java

import static java.util.Arrays.asList;

import java.util.HashSet;
import java.util.Set;

public class VowelsCounter {

  private static final Set<Character> vowels = new HashSet<>(asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

  public static String getBiggestSubstring(final String string, final int k) {
      String biggestSubstring = "";
      int biggestVowelsCounter = 0;

      StringBuilder current = new StringBuilder();
      int currentCounter = 0;

      for (int i = 0; i < string.length(); i++) {
          if (current.length() == k) {
              if (currentCounter > biggestVowelsCounter) {
                  biggestSubstring = current.toString();
              }

              if (vowels.contains(current.charAt(0))) {
                  currentCounter--;
              }
              
              current.deleteCharAt(0);
          }

          final char letter = string.charAt(i);

          if (vowels.contains(letter)) {
              currentCounter++;
          }

          current.append(letter);

          if (biggestVowelsCounter == k) {
              break;
          }

      }

      return biggestSubstring;
  }

  public static void main(String[] args) {
      System.out.println(VowelsCounter.getBiggestSubstring("caberqiitefg", 5));
      System.out.println(VowelsCounter.getBiggestSubstring("caberqjalskjdalskjdalskjdalskjdalsjdalsjdiueoriejwn,dhuyeqooidsqwmliausaspçqlwkeiitefg", 12));
  }
}

[mabranches]

se colocar java logo depois dos 3 ` ele vai deixar colorido com a sintaxe da linguagem. como eu fiz no meu comentario.

[duduribeiro]

@leofachetti editei sua resposta para colocar syntax highlight 👍