В общем, вот тот алгоритм для Valid Parentheses.
O(n) - time complexity
O(1) - space complexity

class Solution {
public:
     bool isMatched (char openBracket,char closeBracket) {
         
        if(openBracket == '(') 
            return closeBracket == ')';
         
        if(openBracket == '{') 
            return closeBracket == '}';
         
        if(openBracket == '[')  
            return closeBracket == ']';
         
        return 0;
     }
    
     bool isValid(string s) {
         
         int top = -1;
         for(std::size_t i = 0; i < s.length(); ++i) {
             
             if(top < 0 || !isMatched(s[top], s[i])) {
                 s[++top] = s[i];
             }
             else {
                 top--;
             }
             
         }
         return top == -1;       
     }
};

тесты?

Ну в leetcode - тесты заходит ))
а вот и само решение от 2018 года - с комментариями, в которых далеко не все согласны по поводу O(1) по памяти )

да, поэтому я и кинул данное решение в этот чат, почему не О(1) по памяти, там индусы какую-то хрень выкладывают, нет нормальных аргументов?!

ну если будет требование неизменности анализируемой строки - bool isValid(string  const& s) то ясно что такое решение не проходит. а так - ну заменили стек на курочение самой строки. я не великий спец, чтобы оценить все тонкости...

Это не O(1). Обычно предполагается, что данные не изменяемые

Вообще, это не правда в корне, представьте какой-нибудь алгоритм сортировки, которой не требуется доп. память, асимптотика, соответственно, такого алгоритма равняется О(1)

кстати да - копия строки создается в предлагаемом решении же.

В общем, мб, я тупой, но я ничего тут на О(n) по доп. памяти не вижу

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

что значит два раза?

два разных запроса?

bool isValid(string s) - при такой сигнатуре? хоть 100 раз.
в функции копия строки создается.

Два раза функцию запустили на одной строке

да это все не важно, нужно смотреть на саму реализацию, ну это проблемы литкода, можно по ссылке принимать и все будет ок

а зачем?
Дана скобочная последовательность, нужно определить, является ли она правильной или нет. Причем тут условие того, что менять содержимое строки нельзя и как это противоречит тому факту, что асимптотика по памяти константная?

Мне вот больше интересно понять, почему фраза "менять содержимое строки нельзя" как-то вмешивается в асимтотический анализ используемой доп. памяти

Так же как считывание массива влияет на асимптотический анализ используемого времени бинпоиска

Кстати, еще такая ассоциация пришла, тогда смысл нам создавать остаточную сеть для того же алгоритма Форда-Фалкерсона, если можно найти макс поток на самом графе...

Просто не понятно, как оно влияет на сам анализ. Получается, это некоторое условие, которое накладывается при выполнении любого алгоритма над какими-то данными?
Что-то, вообще, очень мутно((