Простая задача с собеседования в Google: Merge Strings Alternately

Задача.

Даны две строки. Необходимо смержить эти строки в одну. При этом символы в результирующей строке должны чередоваться: один символ из первой строки, затем один символ из второй строки, и так далее. Если строки разной длины, то оставшиеся символы из более длинной строки должны быть добавлены в конец результирующей строки.

Примеры:

Для строк "abc" и "pqk" результирующая строка будет "apbqck".
Для строк "abc" и "p" результирующая строка будет "apbc".

Ссылка на leetcode: https://leetcode.com/problems/merge-strings-alternately

Решение

Когда в условии задачи фигурируют две строки, два массива, два списка, то наиболее вероятным решением будет применения Two Pointers. Тем более если в условии задачи есть слово "смержить".
Еще одним соображением может быть применение части из алгоритма сортировки Merge Sort. Смотри тут список алгоритмов, которые нужно знать наизусть для собеседования по алгоритмам: Шпаргалка по основным алгоритмам для алгоритмического собеседования.
Можно подумать как адаптировать метод merge из алгоритма Merge Sort:

private static void merge(int[] arr, int left, int mid, int right, int buffer[]) {
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] > arr[j]) {
            buffer[k++] = arr[j++];
        } else {
            buffer[k++] = arr[i++];
        }
    }
    while (i <= mid) {
        buffer[k++] = arr[i++];
    }
    while (j <= right) {
        buffer[k++] = arr[j++];
    }
    k = 0;
    for (i = left; i <= right; i++) {
        arr[i] = buffer[k++];
    }
}

Этот метод также использует подход Two Pointers.

Как мы можем адаптировать этот метод для нашей задачи?

Мы можем инициализировать два указателя: первый будет указывать на начало первой строки, а второй — на начало второй строки. Затем будем поочередно копировать символы: сначала из первой строки, увеличивая первый индекс, затем из второй строки, увеличивая второй индекс. Как только мы достигнем конца одной из строк, результирующую строку дополним оставшимися символами из более длинной строки.

Давайте реализуем этот подход в коде:

    public String mergeAlternately(String word1, String word2) {
        StringBuilder sb = new StringBuilder();
        //Инициализируем два указателя
        int i = 0;
        int j = 0;
        while (i < word1.length() && j < word2.length()) {
            //Копируем символ из первой строки и увеличиваем первый индекс
            sb.append(word1.charAt(i++));
            //Копируем символ из второй строки и увеличиваем второй индекс
            sb.append(word2.charAt(j++));
        }
        //Копируем оставшився хвост из большей строки, если он есть
        while (i < word1.length()) {
            sb.append(word1.charAt(i++));
        }
        while (j < word2.length()) {
            sb.append(word2.charAt(j++));
        }
        return sb.toString();
    }

Временная сложность: O(N+M), где N - длинна первой строки, M - длинна второй строки.
Сложность по памяти: O(1), если не считать память на результирующую строку. Если считать, то O(N+M).

Можно ли улучшить данное решение?

В любом случае нам придется итерироваться по всем элементам обеих строк. Поэтому улучшить временную сложность или сложность по памяти не удастся.
Но можно немного укоротить код решения. Можно заметить, что оба указателя одновременно пробегают одни и теже значения одновременно. Поэтому можно обойтись одним указателем, вместо двух.
Более того, можно объеденить все три цикла в один с дополнительной проверкой, что мы не достигли конца строки, перед копированием символа.

Код решения:

    public String mergeAlternately(String word1, String word2) {
        StringBuilder sb = new StringBuilder();
        //Инициализируем один индекс для итерации по двум строкам
        int i = 0;
        //Заменяем условие в цикле с and на or, чтобы объединить все три цикла в один
        while (i < word1.length() || i < word2.length()) {
            if (i < word1.length()) {
                sb.append(word1.charAt(i));
            }
            if (i < word2.length()) {
                sb.append(word2.charAt(i));
            }
            i++;
        }
        return sb.toString();
    }

Временная сложность: O(N+M), где N - длинна первой строки, M - длинна второй строки.
Сложность по памяти: O(1), если не считать память на результирующую строку. Если считать, то O(N+M).

Давайте посмотрим, как это будет работать шаг за шагом на примере двух строк: "abc" и "pq".

Инициализируем i = 0:

i меньше длинны обеих строк, потому копируем первый символ из первой строки и первый символ из второй строки, и увеличиваем i на единицу:

i меньше длинны обеих строк, потому копируем вторые символы из первой и второй строк и увеличиваем i на единицу:

Теперь i меньше длинны первой строки, поэтому копируем третий символ из первой строки. Но i равно длинне второй строки, поэтому не ничего не делаем со второй строкой:

После этого i = 3, что больше или равно длинны обеих строк. Поэтому на этом работа алгоритма завершается.