Você pode utilizar as `Collections` do `Java` em seu favor da seguinte forma:

    public static void main(String[] args) {
      Map<String, Integer> ocorrencias;

      ocorrencias = contar("Vê se tira notas boas!");
      ocorrencias.forEach((chave, valor) -> System.out.print(chave + ":" + valor + " "));
    }

    private static Map<String, Integer> contar(String frase) {
      Map<String, Integer> resultado = new TreeMap<>(); // TreeMap para manter o Map ordenado pelas chaves
      List<String> ocorrencias;
      Set<String> letras;

      ocorrencias = Arrays.asList(frase.replace(" ", "").split("")); // Transforma a frase em uma lista que facilitará a contagem
      letras = new TreeSet<>(ocorrencias); // Pega as letras sem duplicidade 

      // Percorre o array de letras sem repetição contando as ocorrências
      letras.forEach((String letra) -> {
        resultado.put(letra, Collections.frequency(ocorrencias, letra));
      });

      return resultado;
    }

O código acima produz:

>     !:1 V:1 a:3 b:1 e:1 i:1 n:1 o:2 r:1 s:3 t:2 ê:1

O `TreeSet` não permite valores duplicados, sendo ótimo para guardar as letras sem repetição. Então um `Map` é preenchido com o valor contado pelo método `frequency`.

Veja funcionando no [**Ideone.com**](https://ideone.com/eAIHVj).

---

**Observação:** Note que seu método conta maiúsculas, minúsculas e acentuadas como sendo letras diferentes. Verifique se realmente é este o comportamento esperado.