You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct stack{
char *items;
int top;
};
#define max 100000
typedef struct stack st;
void push(st *stk,char c){
if(stk->top==max-1){
return;
}
else{
stk->items[++stk->top]=c;
}
}
void pop(st *stk){
if(stk->top==-1){
return;
}
else{
stk->top--;
}
}
char * removeDuplicates(char * s){
st *str;
int l=strlen(s);
str=malloc(sizeof(st));
str->items=malloc(l*sizeof(char));
int i;
str->top=-1;
for(i=0;i<l;++i){
int flag=0;
int j=i+1;
while(s[j]==s[i]){
j++;
flag=1;
}
if(s[i]==str->items[str->top]){
pop(str);
}
else if(flag==0){
push(str,s[i]);
}
else{
i=j-1;
}
}
str->items[str->top + 1]='\0';
return str->items;
}
================================================================= ==31==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000004f at pc 0x560f21617b67 bp 0x7fff66262090 sp 0x7fff66262080 READ of size 1 at 0x60200000004f thread T0 #2 0x7f93db0310b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) 0x60200000004f is located 1 bytes to the left of 6-byte region [0x602000000050,0x602000000056) allocated by thread T0 here: #0 0x7f93dbc76bc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8) #3 0x7f93db0310b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) Shadow bytes around the buggy address: 0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 =>0x0c047fff8000: fa fa 07 fa fa fa 00 00 fa[fa]06 fa fa fa fa fa 0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa Shadow byte legend (one shadow byte represents 8 application bytes): Addressable: 00 Partially addressable: 01 02 03 04 05 06 07 Heap left redzone: fa Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 Container overflow: fc Array cookie: ac Intra object redzone: bb ASan internal: fe Left alloca redzone: ca Right alloca redzone: cb Shadow gap: cc ==31==ABORTING