Use stacks. Push one letter by letter. If stack.top() == current letter, pop the stack. else push the letter in the stack. #include<bits/stdc++.h> using namespace std; stack<char> S; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s; cin >> s; int len = s.length(); for(int i = 0; i < len;i++) { char c; if(S.empty()) c = 0; else c = S.top(); if(c == s[i]) S.pop(); else S.push(c); } string ans = ""; len = S.size(); for(int i = 0; i < len;i++) { char c = S.top(); ans += c; S.pop(); } reverse(ans.begin(),ans.end()); cout << ans; } You should do S.push(s[i]) in your else clause inside the for loop. For Time limit exceeded: If you get time limit exceeded, it must mean that you're trying to modify the input string (i.e. trying to delete i-th chars). Try creating a new OUTPUT string without modifying the INPUT string. Note: if you're using a high language such as java or C#, try using the StringBuilder object to build your output string. For Wrong Answer(WA): If you get WA, try some of these test cases: Input: "dddd" Output: "" Input: "ddddd" Output: "d" Input: "abba" Output: "" Input: "abbbbac" Output: "c" Input: "wliisddsmmleeddw" Output: "" Input: "avcbbffcv" Output: "a" Hope this helps. Edited by author 12.07.2012 00:47 Input: "abbbbac" Output: "c" Спасибо, помогло! For Time limit exceeded: If you get time limit exceeded, it must mean that you're trying to modify the input string (i.e. trying to delete i-th chars). Try creating a new OUTPUT string without modifying the INPUT string. Note: if you're using a high language such as java or C#, try using the StringBuilder object to build your output string. For Wrong Answer(WA): If you get WA, try some of these test cases: Input: "dddd" Output: "" Input: "ddddd" Output: "d" Input: "abba" Output: "" Input: "abbbbac" Output: "c" Input: "wliisddsmmleeddw" Output: "" Input: "avcbbffcv" Output: "a" Hope this helps. Edited by author 12.07.2012 00:47 Thanks a lot...I could'n understand the problem statement first, now, reading ur comment I clearly understood the problem. for me problem was that program was returning "axx" on "aaaxx" Edited by author 18.03.2017 19:56 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cmath> #include <algorithm> #include <set> #include <vector> #include <string> #include <cstdlib> using namespace std; void optimization() { cin.tie(nullptr); ios_base::sync_with_stdio(false); } int main() { optimization(); string s; int k = -1; cin >> s; char c[200000]; for (char & i : c) { i = ' '; } for (char i : s) { if (k > -1) { if (c[k] == i) { c[k] = ' '; k--; } else { k++; c[k] = i; continue; } } else { k++; c[k] = i; } } for (char i : c) { if (i != ' ') { cout << i; } } return 0; } #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MAX = 1e5+10; const ll ZERO = 0; #define endl '\n' #define dokme(x) cout << x ; return(0); #define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); stack < char > stk; int main(){ migmig; stk.push('.'); char c[200001]; cin >> c; int n=strlen(c); for (int i =0; i < n ; i ++ ){ if (stk.top()!=c[i]){ stk.push(c[i]); } else{ stk.pop(); } } n=stk.size()-1; memset(c,0,sizeof(c)); for (int i = 0 ; i<n ; i ++ ){ c[n-i-1]=stk.top(); stk.pop(); } cout << c; } #include <iostream> #include <cstdlib> #include <deque> using namespace std; int main() { int h; char s[200001]; scanf("%s", &s); int n=strlen(s); deque<char> v (s, s + n );
if(v.size()==2 && v[0]==v[1] ) return 0; b: h=2; for(int i=0; i<v.size()-1 ;i++) if(v[i] == v[i+1]) { v.erase(v.begin() + i); v.erase(v.begin() + i); h=1; } if(h==1) goto b;
for(int i=0; i<v.size(); i++) cout << v[i];
return 0; } Hello, If you are still working on this, let you know that it can't be solved with erase. I implemented a similar algorithm in Java which goes through the string and deletes the successful characters and it also got TLE on test 6.The easiest way is removing the successful characters as you read them. nc->new character from the input. if(i!=-1&&c[i]==nc){//new char is equal to the char at the end of the string, remove it i--; }else{ //add the new char to the string i++; c[i]=nc; } Hope this helps You got TLE because deque has poor deletion performance on positions other than the front and back. #include<iostream> #include<string.h> #include<deque> #include<stdio.h> using namespace std; int main() { string node; cin >> node; int one,two; one = 0; two = 1; int pre = 0; for(int i = 0;i < node.size();i++) { if(node[i] == '!') continue; if(node[i] == node[i+1]) { node[i] = node[i+1] = '!'; one = pre; if(i+2 < node.size()) two = i+2; while(one> 0 && two < node.size()) { while(one > 0 && node[one] == '!') one--; if(node[one] == node[two] ) { node[one] = node[two] = '!'; one--;two++; } else break; } } else pre = i; }
for(int i = 0;i < node.size();i++) { if(node[i] != '!') cout << node[i]; }
} I use stack and my solution works 0.064s :) My solution works 0.048s ;) Why your solutions is right? if input is: sddssdds then your ans is "ss"! For test you can use this string: hkjgnnngkikipipekkfkfgg Correct result is: hkjgngkikipipefkf using System; namespace pain { class Program { static void Main(string[] args) { string s = Console.ReadLine(); char[] ss = new char[s.Length]; for (int i = 0; i < s.Length; i++) ss[i] = s[i]; for (int i = 0; i < s.Length - 1;) { if (ss[i] == ss[i + 1]) { if (i - 1 >= 0) { int n = i + 2; b: if (n <= s.Length - 1) { if (ss[n] != ' ') { ss[i] = ss[n]; ss[n] = ' '; ss[i + 1] = ' '; } else { n++; goto b; } } else break; } else { ss[i] = ' '; ss[i + 1] = ' '; } if (i >= 1) i--; else i++; } else i++; } for (int i = 0; i < s.Length; i++) if(ss[i] != ' ') Console.Write(ss[i]); //Console.Write(st2(s)); Console.ReadLine(); } public static string st1(string s, ref int n) { if (s.Length - 1 > n) { if (s[n] == s[n + 1]) { s = s.Remove(n, 2); if (n >= 2) n -= 2; else n--; } n++; s = st1(s, ref n); } return s; } public static string st2(string s) { for (int i = 0; i < s.Length - 1; i++) { if (s[i] == s[i + 1]) { s = s.Remove(i, 2); if (i >= 2) i -= 2; } } return s; } public static string st3(string s) { int n = 0; int nt = s.Length - 1; string[] ss = new string[nt]; for (int i = 0; i < nt; i++) { bool d = false; for (int j = i; j < nt; j++) { if (ss[i] == s[j].ToString()) { d = true; } } if (!d) { ss[n] = s[i].ToString(); n++; } } n = 0; while (nt != 0) { nt = s.Length; for (int i = 0; i < ss.Length; i++) { s = s.Replace(ss[i] + ss[i], ""); } if (nt == s.Length) break; } return s; } } } Edited by author 02.04.2019 03:06 Why Wring answer? import java.util.Scanner; public class T1654 { public static char[] arr; public static String out = ""; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); String inp = sc.next(); sc.close(); arr = new char[inp.length()]; arr = inp.toCharArray(); format(); if(out != "") { System.out.println(out); } else { System.out.println(""); }
}
public static void format() { boolean isFormat = false; int l = arr.length; for(int i = 0; i< l-1; i++) { if(arr[i] == arr[i+1]) { arr[i] = 0; arr[i+1] = 0; isFormat = true; } else if(arr[i] != arr[i+1] & arr[i] != 0){ out += arr[i]; } } out+= arr[arr.length-1]; if(isFormat == true) { arr = new char[out.length()]; arr = out.toCharArray(); out = ""; format(); } } } import random letters = ['a' ,'b' ,'c' ,'d' ,'e' ,'f' ,'g' ,'h' ,'i' ,'j' ,'k' ,'l' ,'m' ,'n' ,'o' ,'p' ,'q' ,'r' ,'s' ,'t' ,'u' ,'v' ,'w' ,'x' ,'y' ,'z'] example = 'xitsa' while len(example) < 199999: letter = random.choice(letters) point = random.randrange(0, len(example)) example = example[:point] + letter + letter + example[point:] print(example) I thought that stack is the best thing in this case but I've seen 0.015 and 0.001 sec . I've got 0.046 Maybe it's because of the choice of language. I use C++17 and it run in 0.001s char[200001] gives perfect time if you will check repeats while string is inputting i used deque. cout got me TLE.using printf save me. if(st.front()!=s[i]) { st.emplace_front(s[i]); } else st.pop_front();
for(it=st.end()-1; it>=st.begin(); it--) { printf("%c",*it); } i say more - it's better don't use stl-containers if it's possible. char[200001] gives perfect time import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Iterator; import java.util.Stack; public class problem1654 { public static void main(String[] args) throws IOException { BufferedReader inp = new BufferedReader(new InputStreamReader(System.in)); String str=inp.readLine(); Stack<Character> st=new Stack<Character>(); st.push(str.charAt(0)); String s=""; for(int i=1;i<str.length();i++){ if(!st.empty()&&st.peek()==str.charAt(i)) st.pop(); else{ st.push(str.charAt(i));
} }
while(!st.empty()){ s=s+st.pop(); } int n=s.length(); for(int i=0;i<n;i++){ System.out.print(s.charAt(n-i-1));
} }} When i used stack(from STL) in C++, i'd got TL8. But after i realzed stack by using array, i got AC your reply help me very much!3Q Don't use : while(!st.empty()){ s=s+st.pop(); } -------- Use this phrase at the end of your Code: Iterator<Character> b = st.iterator(); while(b.hasNext()){ System.out.print(b.next()); } // Harry Poter #include <stdio.h> #include <iostream> #include <stdlib.h> #include <string.h> using namespace std; int main() { char line[200001], w2[200001]; cin.getline(line, sizeof(line)); int t = 0, i; for(i = 0; i < strlen(line); i++){ if (line[i] == line[i + 1]) { i++; A: if (line[i + 1] != line[i + 2]) { if (t != 0 && w2[t - 1] == line[i + 1]) {t--; i += 1; goto A;} } } else {w2[t++] = line[i];} } w2[t] = '\0'; printf("%s", w2); } The test is "abcdeedcbaabcdeedcba"(without quotes). The answer should be ""(empty string). hey mi anwser code is the same, what is the bug hey if one else to know print the anser plese say me..in the test #4 i have a empty string, but the judge say me "wa" in test #4.... why??? help me please. #include <bits/stdc++.h> using namespace std; int main(){ string cad,res; cin>>cad; res = ""; int tam = cad.length(); int i,j; i=0; j=1; int boolean[tam]={0}; while(j<tam){ if(cad[i]==cad[j]){ boolean[i] = 1; boolean[j] = 1; if(i-1>=0){ i-=1; j+=1; }else{ i=j+1; j+=2; } }else{ i=j; j+=1; } } for(int i=0;i<tam;i++){ if(boolean[i]==0) res+=cad[i]; } cout<<res; return 0; } Can any body tell me whai is in the test case 5...??? My code seems right but everytime it says WA#5... 200000 char in test case #5!! Thanksss.. It helped me a lot... Edited by author 25.12.2015 13:35 import java.util.Scanner; import java.util.Stack; public class CliperMessage_1654_Stack { public static void main(String[] arg1) { Scanner sc=new Scanner(System.in); StringBuilder sb=new StringBuilder(); Stack<Character> stc=new Stack<>(); sb.append(sc.nextLine()); if(sb.length()<=200000){ for(int i=0;i<sb.length();i++){ if(stc.isEmpty()||(stc.peek()!=sb.charAt(i))) stc.push(sb.charAt(i)); else if((stc.peek()==sb.charAt(i))) stc.pop();
}
StringBuilder sbn=new StringBuilder(); int j=0; while(!stc.empty()) sbn.insert(j++, ""+stc.pop()); System.out.println(sbn.reverse()); } } } |
|