Ті дві речі можна вирішити заздалегідь. І тоді це вже не так стрьомно :)

Але, імхо, специфічні дані та будь-якого роду едж кейси та ліміти потрібно перевіряти незалежно від того, який у вас алгоритм.

Так, погоджуюсь. Мемоїзація не є унікальним атрибутом рекурсивних алгоритмів.
Імхо, унікальним атрибутом саме рекурсивних алгоритмів є можливість розділити проблему на підпроблему. В деяких випадках то може допомогти написати більш оптимальний алгоритм. ДП проблеми легше почати вирішувати з рекурсивного алгоритму, а потім просто приходити до ітеративного із масивом чи ще чимось, що зберігає проміжні результати, якщо є така можливість.

Уже в формулировании условия задачи огромная дыра. Нет условия сберечь максимальное количество символов. Т.е. АВВВВВВВВВВВВ -> А.

Ця умова не потрібна, тому що є

видаляє всі комбінації AB, BA, CD, DC;

Якщо функція поверне A для АВВВВВВВВВВВВ, то вона працює неправильно.

Додам ще цей алгоритм, він працює швидше ніж інші два ітеративні завжди, але на повторюваному інпуті все одно працює повільніше ніж рекурсивні. Можете додати свій варіант тут чи на гітхабі. Думаю, що на наступному тижні зможу провести ще додаткові рани — додам результати.

Нажаль такого досвіду не маю.
Але саме формат даних ви повинні знати заздалегідь, якщо плануєте працювати із ними. Характер даних, якщо не може бути з’ясований заздалегідь, можна вирахувати, якщо є статистика по тим даним. Впевнений, що data analyst зможе порахувати то без проблем.

На гроші я в таке грати не буду. Але я подивлюсь, що можна написати. Якщо то дійсно гон, то ок, my bad :)

Ви кожен раз маєте O(n) на пошук в хеш мапі. Або коли рахуєте хеш, або якщо ви замість хеш фунції повноцінної зробили оцей аналог return 0 — то O(n) буде при колізії в хеш мапі. Він у вас нікуди не подівся.

Ось це буде ЛИШЕ в найгіршому випадку із неоптимізованою хеш функцією.
Пошук в хешмапі рівний до O(n) буде лише у worst case scenario, коли саме таблиця є ДУЖЕ малою. Але ж ви мене не чуєте. Колізії в таблиці розміром 2 ** 64 будуть за дуже великим виключенням. І це типу вже від вас залежить, чи рахувати хеш із всього інпуту чи ні.

Бтв, то я реально вперше бачу, щоб хтось так сильно відстоював свою точку зору, що put/find в хешмапі — то O(n). Зазвичай то амортизована O(1). Ви на роботі не використовуєте хешмапу через те, що вона повільна?

Ще раз. В кращому випадку (ABABABABABABABAB) буде O(logn)

replace(ABABABABABABABAB)
replace(ABABABAB)
replace(ABAB)
replace(AB) -> return ""
replace(AB) -> return «"
replace(ABAB) -> return «„. Результат цього інпуту в нас вже є.
replace(ABABABAB) -> return “», тому що ми вже знаємо результат з попереднього колу. Все. Тобто половину інпуту ми навіть не перевіряємо.

Ваш закид про хеш функцію — душна спроба вийти правим.

Ні, ви сказали що можна хеш функцію написати, яка буде скейлитись константно. Але це неможливо.

Та як це неможливо? Ви ж розумієте, що в певних випадках навіть просто перша літера сабстрінги помножена на довжину сабстрінги вже може бути хеш функцією за певних умов? І буде рахуватись константно незалежно від довжини інпуту. А ви кажете неможливо.

Це ніяк не міняє суті. Пройти ввід доведеться весь.

Якби ви знали, що певний інпут складається лише із двох літер, ви б теж його хешували як звичайний стрінг?

Я не казав, що ігнорувати потрібно. Я казав, що можна написати хеш функцію таку, котра буде задовольняти вас по швидкості. Вона може враховувати специфічний інпут, як от лише чотири літери — блок із 4 літер буде займати лише 1 байт. Так само можна враховувати довжину інпуту. Наприклад кількість повних пар в цьому інпуті. І враховувати лише певну кількість блоків літер, якщо ви так переймаєтесь перформансом.
Хеш колізії будуть, звісно. Але вони будуть і з стандартними хеш-функціями і то не є чимось, що аж так сильно впливає на перформанс.
Але (!) враховуючи все це рекурсивний алгоритм все одно буде O(logn) в бест кейс сценаріо — ABABABABABABABABABABA та O(n) в ворст кейс — AAAAAAAAAABBBBBBBBBB.

І з рекурсивним алгоритмом бест кейс сценаріо НЕ буде проходити всі літери — воно навіть і половини літер проходити не буде. Тобто коли ви кажете, що

Як не крути, доведеться пройти ВСІ символи в стрічці, це О(н), і цього в принципі в цій задачі уникнути неможливо.

 то це просто брехня.

Якщо не вмієте в рекурсивні функції, так і скажіть ;)

Оце класний жарт. Прямо таки неможливо. Не думаю, що тут можна щось ще обговорювати.

Якщо то буде вже такою великою проблемою, можна написати свою хеш функцію, котра буде рахувати код за константний час. На великих даних це все одно буде швидше, ніж проходити одні й ті самі сабстрінги.
Але, імхо, аргумент, що не варто використовувати хешмеп, тому що хеш функція повільна, то щось новеньке.

Ще раз із прикладом:
пишу, як будуть відбуватись коли
в хеш мапу одразу додаємо значення {
“AB”: “‘,
‘BA’: ‘‘,
і т.д.

ABBAABBABBBABABA

replace(ABBAABBA)
replace(ABBA) -> returned ’’, added ‘ABBA’ to hashmap
replace(AB) -> returned ’”
replace(BA) -> returned ""
replace(ABBA) -> returned “" since “ABBA” already in hashmap
replace(BBBABABA) ->
replace(BBBA) ->
replace(BB) -> return “BB”
replace(BA) -> return “"
replace(BBBA) -> returned “BB”, “BBBA” added to hashmap
replace(BABA) -> “‘, ‘BABA’ added to hashmap
replace(BA) -> ’”
replace(BA) -> ""

що ми бачимо.
повторювані комбінації інпуту не обробляються взагалі, тому що результат вже є. Так, звісно, на якихось унікальних інпутах, де комбінації не будуть повторюватись взагалі, то буде О(n). Але саме average та при збільшенні інпуту, то может бути O(logn).

???

Ми ж не кожну літеру будемо туди перекладати. Але навіть якщо і кожну, їх там чотири всього.
insert — O(1)
find — O(1)

Якщо будемо зберігати результати у хеш мапі після кожного виклику рекурсивного методу, то не доведеться проходити по всіх символах. В цьому ж і суть.
(ABBAABBABBBABABA) — рандомний інпут, але лише із двома літерами для прикладу
(ABBAABBA) (BBBABABA)
(ABBA) (ABBA) (BBBA) (BABA)
(AB)(BA) () (BB)() ()()

Підхід такий, що результат виклику рекурсивної функції для інпуту AB та BA, а потім і ABBA ми вже знаємо — немає сенсу йти далі для наступного рекурсивного кола. І подібних спрощень буде лише більше на великому інпуті враховуючи обмеженість набору літер.

Так, це дійсно буде дуже простий алгоритм та ефективний. Але це буде O(n). Рекурсивний алгоритм із мемоізацією результатів підпроблем на великих інпутах буде O(logn) в середньому. У випадку ААААВВВВ то звісно буде лінійна складність.

На інпуті ABABA немає різниці, яку комбінацію спершу видаляти. Але так, то звісно не доказ. Сюди потрібен якийсь math geek, котрий зможе довести це математично :)

В умовах задачі нічого не сказано про порядок того, як і що видаляти.
Так і в тому і сенс, що ми розбиваємо проблему на дві підпроблеми, кожна за яких може вирішуватись (ABAB), а може ніт. Тобто місце, де з’єднуються результати двох підпроблем, є єдиним місцем, де можуть виникнути комбінації.
І звісно, що видалення комбінацій після з’єднання повинно відбуватись лише у випадку, якщо там вони є.

Буде efficient, якщо після replace(left) та replace(right) перевірити adjacent літери. В найгіршому випадку (AAAABBBB) то буде O(n). Але ж O(n) і в тих алгоритмах, що описані в статті навіть в кращих випадках.

Імхо, саме такий алгоритм і повинен запропонувати кандидат одразу. Розділяти можна просто порівну. Якщо розділення відбудеться по комбінації, котру ми шукаємо, то вона або вже не буде актуальною після процесінгу двох половин, або вирішиться після з’єднання.
Враховуючи, що літери лише 4, то додаючи hash мапу із вхідним параметром та результатом, алгоритм буде оптимізованим. В гіршому випадку буде O(n), в кращому (це коли перша половина інпуту так сама як і друга) O(logn).

Тому що міф про те, що «60k в Україні краще ніж 300к в США» вже десятки разів обговорювався і спростовувався.