[백준] 9935번: 문자열 폭발

https://www.acmicpc.net/problem/9935

initial

So this is popping substrings from an original string. I used .replace() method originally but the time complexity of .replace() is nm, where n and m are lengths of the 2 strings. .replace() works by first iterating through the original string o(n). Then, it creates a new string, which takes n+m time. If there are k occurrences of this substring, then it is k*(n+m).

original runtime but correct:

original = input()
hola = input()

while hola in original:
    original = original.replace(hola, "")

if len(original) == 0:
    print("FRULA")
else:
    print(original)

So we cant use this for a long string cuz time eff is bad. I looked at the hint and saw stack. Actually I thought of stack cuz this is similar to bracket popping question but my stack deque can’t be sliced … right? Yes you cant slice deque via the index but if you implement stack with a list, not a deque, then you can slice via index just like a regular list!! I didnt know this cuz i have always been implementing stack with deques.

Another thing is I placed an additional check where stack must have a greater length than the substring’s length. But apparently you dont need this check cuz if you have at least 1 element in your stack,

for i in x:
    stack.append(i)
    if stack[len(stack)-m:len(stack)] == M: 

This works without additional check cuz stack[-4:1] is valid. BUT if you have no element at all in your stack, it causes error. But i still prefer placing the condition cuz i have dealt with index out of range error for too long.

revisited may 12th

yes well explained and i retried successfully after 2 days of relooking at solution

revisited jun 27th

easy

solution

from collections import deque
import sys
original = list(sys.stdin.readline().strip())
substring = list(sys.stdin.readline().strip())
stack= []

for i in original:
    stack.append(i)
    
    if len(stack) >= len(substring):
        if stack[-len(substring):] == substring:
            for _ in range(len(substring)):
                stack.pop()

if stack:
    print(*stack,sep='')
else:
    print("FRULA")

complexity

Time Complexity:
Reading Input (O(n+m)): Reading the original and substring strings takes O(n+m) time, where n and m are the lengths of the strings.
Loop Over Characters (O(n)): The loop iterates through each character in the original string, where n is the length of the original string.
Inner Loop (Worst Case: O(m n)): The inner loop (range(len(substring))) can iterate up to the length of the substring for each character in the original string.
The overall time complexity is dominated by the worst-case scenario of the inner loop: O(m n).

Space Complexity:
List original (O(n)): The original list stores the characters of the original string.
List substring (O(m)): The substring list stores the characters of the substring.
List stack (O(n)): The stack list stores characters from the original string. In the worst case, it can be the same length as the original string.
The overall space complexity is O(n + m).

Keep in mind that the time complexity could be improved by using more efficient string manipulation techniques, as discussed in earlier responses. The space complexity is dominated by the input and the size of the stack.