Поиск уникальных букв в множестве строк. C#

Question

Есть такая задача:

Джон нашел коллекцию камней. Каждый камень состоит из нескольких элементов, представленных маленькими латинскими буквами: от 'a' до 'z'. Элемент может входить в состав камня несколько раз. Элемент называется "драгоценным", если он входит хотя бы один раз в состав каждого камня. Дан список составов камней. Требуется найти число "драгоценных" элементов, присутствующих в этих камнях.

Решение "в лоб" (которое прошло тесты):

public static int SomeFunc(List<string> arr)
    {
        int result = 0;
        string latinChars = "abcdefghijklmnopqrstuvwxyz";

        for (int i = 0; i < 26; i++)
        {
            if (arr.All(s => s.Contains(latinChars[i])))
            {
                result++;
            }
        }
        return result;
    }

Потом пришел к мысли, что можно взять самую короткую строку и использовать ее в качестве отправной точки:

public static int SomeFunc(List<string> arr)
    {
        int result = 0;
        var shortestString = arr.FirstOrDefault(x => x.Length == arr.Min(s => s.Length));
        
        for (int i = 0; i < shortestString.Length; i++)
        {
            if(arr.All(s => s.Contains(shortestString[i])))
            {
                result++;
            }
        }
        return result;
    }

Но здесь есть ошибка, до которой не получается додуматься - этот вариант прошел половину тестов. Подскажите, где зарыта собака? P.S. приведение к регистру здесь не нужно.

Answer 1

Если в самой короткой строке один символ встречается больше одного раза и он драгоценный, то он будет посчитан столько раз, сколько встречается. Для начала нужно "нормализовать" строку, т.е. удалить все повторы символов.

Answer 2

Вызов Contains по идее сканирует всю строку, то есть если самое короткое слово будет длиной 1000, то на каждое другое слово будет 1000 сканов по тексту 1000 длины, то есть каждый символ кажддой строки будет сравниваться с чем то 1000 раз или миллион сравнений в сумме.

Можно поробовать индексировать строки, завести массив счетчиков каждого символа и обновлять этот массив для каждой из строк. Тогда каждый символ будет считан только 1 раз. Выглдяит это как то так

public static int SomeFunc(List<string> arr)
{
    int result = 0;
    int[] counters = new int[26];

    for (int i = 0; i < arr.Count; i++)
    {
        foreach (var c in arr[i])
        {
            int ind = c - 'a';
            if (counters[ind] == i) counters[ind]++;
        }
    }

    for (int i = 0; i < counters.Length; i++)
        if (counters[i] == arr.Count) result++;
        
    return result;
}

Ничего более быстрого по асимптотике мне в голову не пришло и навряд ли вообще можно решить задачу асимптотически быстрее.

БЛОГ НА HUSL

Поиск уникальных букв в множестве строк. C#

Ответы (2 шт):