Remove Pattern Repeatedly

Remove Pattern Repeatedly

Hard Programming Interview Data Structures 14 views
Explanation Complexity

Problem Statement

Input provides {x}. Remove every occurrence of p from s while scanning left to right (like stack remove). Output final string.

Input Format

Two lines: s then p.

Output Format

One line result.

Example

daabcbaabcbc
abc
dab

Constraints

Total length

Input / Output Format

Input Format
Two lines: s then p.
Output Format
One line result.
Constraints
Total length

Examples

Input:
daabcbaabcbc abc
Output:
dab

Example Solution (Public)

Programming Interview 
import sys
lines=sys.stdin.read().splitlines()
if len(lines)<2: sys.exit(0)
s=lines[0].strip()
p=lines[1].strip()
if p=='':
  sys.stdout.write(s)
  sys.exit(0)
L=len(p)
stack=[]
for ch in s:
  stack.append(ch)
  if len(stack)>=L and stack[-L:]==list(p):
    del stack[-L:]
sys.stdout.write(''.join(stack))

Official Solution Code

import sys
lines=sys.stdin.read().splitlines()
if len(lines)<2: sys.exit(0)
s=lines[0].strip()
p=lines[1].strip()
if p=='':
  sys.stdout.write(s)
  sys.exit(0)
L=len(p)
stack=[]
for ch in s:
  stack.append(ch)
  if len(stack)>=L and stack[-L:]==list(p):
    del stack[-L:]
sys.stdout.write(''.join(stack))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.