Remove all adjacent duplicates
For this problem, I came up with this ugly solution of appending the characters to the output and in case there is adjacent duplicate deleting from the output. Considering StringBuilder.deleteCharAt(i)
is O(N), performance is O(N) + O(N) = O(N).
Please critique this, if this is a right way.
public static String removeDuplicate(String s) {
StringBuilder builder = new StringBuilder();
char lastchar = '';
for (int i = 0; i < s.length(); i++) {
String str = builder.toString();
if (!str.equals("")
&& (str.charAt(str.length() - 1) == s.charAt(i))) {
builder.deleteCharAt(str.length() - 1);
} else if (s.charAt(i) != lastchar)
builder.append(s.charAt(i));
lastchar = s.charAt(i);
}
return builder.toString();
}
Sample input outputs:
Input: azxxzy
Output: ay
Input: caaabbbaacdddd
Output: Empty String
Input: acaaabbbacdddd
Output: acac
java algorithm performance
add a comment |
For this problem, I came up with this ugly solution of appending the characters to the output and in case there is adjacent duplicate deleting from the output. Considering StringBuilder.deleteCharAt(i)
is O(N), performance is O(N) + O(N) = O(N).
Please critique this, if this is a right way.
public static String removeDuplicate(String s) {
StringBuilder builder = new StringBuilder();
char lastchar = '';
for (int i = 0; i < s.length(); i++) {
String str = builder.toString();
if (!str.equals("")
&& (str.charAt(str.length() - 1) == s.charAt(i))) {
builder.deleteCharAt(str.length() - 1);
} else if (s.charAt(i) != lastchar)
builder.append(s.charAt(i));
lastchar = s.charAt(i);
}
return builder.toString();
}
Sample input outputs:
Input: azxxzy
Output: ay
Input: caaabbbaacdddd
Output: Empty String
Input: acaaabbbacdddd
Output: acac
java algorithm performance
6
Why does it have to be recursive? ... and if it has to be recursive, why is your code not recursive?
– rolfl♦
Mar 6 '14 at 0:31
1
Additionally, what does it mean to remove duplicates? If I give your code the wordmessy
it returnsmey
... I was expectingmesy
... which one is right? Why?
– rolfl♦
Mar 6 '14 at 0:34
@rolfl The examples added in Rev 2 clarify both issues."messy"
→"mey"
. "Recursively remove" refers to the problem statement, not the implementation.
– 200_success
Mar 6 '14 at 5:58
add a comment |
For this problem, I came up with this ugly solution of appending the characters to the output and in case there is adjacent duplicate deleting from the output. Considering StringBuilder.deleteCharAt(i)
is O(N), performance is O(N) + O(N) = O(N).
Please critique this, if this is a right way.
public static String removeDuplicate(String s) {
StringBuilder builder = new StringBuilder();
char lastchar = '';
for (int i = 0; i < s.length(); i++) {
String str = builder.toString();
if (!str.equals("")
&& (str.charAt(str.length() - 1) == s.charAt(i))) {
builder.deleteCharAt(str.length() - 1);
} else if (s.charAt(i) != lastchar)
builder.append(s.charAt(i));
lastchar = s.charAt(i);
}
return builder.toString();
}
Sample input outputs:
Input: azxxzy
Output: ay
Input: caaabbbaacdddd
Output: Empty String
Input: acaaabbbacdddd
Output: acac
java algorithm performance
For this problem, I came up with this ugly solution of appending the characters to the output and in case there is adjacent duplicate deleting from the output. Considering StringBuilder.deleteCharAt(i)
is O(N), performance is O(N) + O(N) = O(N).
Please critique this, if this is a right way.
public static String removeDuplicate(String s) {
StringBuilder builder = new StringBuilder();
char lastchar = '';
for (int i = 0; i < s.length(); i++) {
String str = builder.toString();
if (!str.equals("")
&& (str.charAt(str.length() - 1) == s.charAt(i))) {
builder.deleteCharAt(str.length() - 1);
} else if (s.charAt(i) != lastchar)
builder.append(s.charAt(i));
lastchar = s.charAt(i);
}
return builder.toString();
}
Sample input outputs:
Input: azxxzy
Output: ay
Input: caaabbbaacdddd
Output: Empty String
Input: acaaabbbacdddd
Output: acac
java algorithm performance
java algorithm performance
edited Mar 9 '14 at 0:47
asked Mar 6 '14 at 0:28
AnujKu
11616
11616
6
Why does it have to be recursive? ... and if it has to be recursive, why is your code not recursive?
– rolfl♦
Mar 6 '14 at 0:31
1
Additionally, what does it mean to remove duplicates? If I give your code the wordmessy
it returnsmey
... I was expectingmesy
... which one is right? Why?
– rolfl♦
Mar 6 '14 at 0:34
@rolfl The examples added in Rev 2 clarify both issues."messy"
→"mey"
. "Recursively remove" refers to the problem statement, not the implementation.
– 200_success
Mar 6 '14 at 5:58
add a comment |
6
Why does it have to be recursive? ... and if it has to be recursive, why is your code not recursive?
– rolfl♦
Mar 6 '14 at 0:31
1
Additionally, what does it mean to remove duplicates? If I give your code the wordmessy
it returnsmey
... I was expectingmesy
... which one is right? Why?
– rolfl♦
Mar 6 '14 at 0:34
@rolfl The examples added in Rev 2 clarify both issues."messy"
→"mey"
. "Recursively remove" refers to the problem statement, not the implementation.
– 200_success
Mar 6 '14 at 5:58
6
6
Why does it have to be recursive? ... and if it has to be recursive, why is your code not recursive?
– rolfl♦
Mar 6 '14 at 0:31
Why does it have to be recursive? ... and if it has to be recursive, why is your code not recursive?
– rolfl♦
Mar 6 '14 at 0:31
1
1
Additionally, what does it mean to remove duplicates? If I give your code the word
messy
it returns mey
... I was expecting mesy
... which one is right? Why?– rolfl♦
Mar 6 '14 at 0:34
Additionally, what does it mean to remove duplicates? If I give your code the word
messy
it returns mey
... I was expecting mesy
... which one is right? Why?– rolfl♦
Mar 6 '14 at 0:34
@rolfl The examples added in Rev 2 clarify both issues.
"messy"
→ "mey"
. "Recursively remove" refers to the problem statement, not the implementation.– 200_success
Mar 6 '14 at 5:58
@rolfl The examples added in Rev 2 clarify both issues.
"messy"
→ "mey"
. "Recursively remove" refers to the problem statement, not the implementation.– 200_success
Mar 6 '14 at 5:58
add a comment |
4 Answers
4
active
oldest
votes
The problem is not that StringBuilder.deleteCharAt()
is O(n) — you only ever use it to strip the last character. Rather, it's your builder.toString()
that is problematic. It's an O(n) operation that is invoked in a loop up to n times.
Rather than using a StringBuilder
, I recommend manipulating a char
array directly. The problem, as you pointed out, is that By doing your own accounting, you can just build the string correctly the first time.StringBuilder.deleteCharAt(i)
is O(n) because it shifts the rest of the string over.
public static String removeDuplicates(String s) {
if (s.isEmpty()) {
return s;
}
char buf = s.toCharArray();
char lastchar = buf[0];
// i: index of input char
// o: index of output char
int o = 1;
for (int i = 1; i < buf.length; i++) {
if (o > 0 && buf[i] == buf[o - 1]) {
lastchar = buf[o - 1];
while (o > 0 && buf[o - 1] == lastchar) {
o--;
}
} else if (buf[i] == lastchar) {
// Don't copy to output
} else {
buf[o++] = buf[i];
}
}
return new String(buf, 0, o);
}
add a comment |
General
Your code formatting is all over the place. You should use consistent and structured indentation. See the Java Code-Style guide for, well, guidance.
if I take your code, and re-format it (Eclipse, CtrlA and CtrlshiftF), it looks like:
public static String removeDuplicate(String s) {
StringBuilder builder = new StringBuilder();
char lastchar = '';
for (int i = 0; i < s.length(); i++) {
String str = builder.toString();
if (!str.equals("") && (str.charAt(str.length() - 1) == s.charAt(i))) {
builder.deleteCharAt(str.length() - 1);
} else if (s.charAt(i) != lastchar)
builder.append(s.charAt(i));
lastchar = s.charAt(i);
}
return builder.toString();
}
At least this allows us to see what you are doing.
Algorithm
A nice algorithm will take data from the input string, and add it to the output if it should be added. A system where you do multiple conversions, add things, and remove things, is complicated, and hard to follow.
Additionally, the null character is actually a valid character in Java, so you may have (an extremely rare) bug.
I do not like that your code is removing all the duplicate values, it seems more practical to remove all but one of the duplicates, but you do not explain why it is supposed to be this way.
More Information required
The above, in itself, is a review, but, if you update your question with the requested details:
- recursion yes/no/why?
- dedup all, or all-but-one?
then I can add suggestions as to how to solve this in a more efficient way.
Actually I had issue while posting the code here, thats why formatting is all over the place. Anyways I follow Google style sheet in my eclipse, so it will be all right.
– AnujKu
Mar 6 '14 at 1:10
The question was : to remove adjacent duplicates from the code. I will post the valid inputs outputs in the question
– AnujKu
Mar 6 '14 at 1:11
add a comment |
Ultimately you have to remove the duplicates from the String without using HashSet. One technique is to sort the char array first. The complete code is:
public class Test3 {
public static void main(String args) {
String str = "ABBCDAABBBBBBBBOR";
char ca = str.toCharArray();
Arrays.sort(ca);
String a = new String(ca);
System.out.println("original => " + a);
int i = 0 ;
StringBuffer sbr = new StringBuffer();
while(i < a.length()) {
if(sbr.length() == 0 ) {sbr.append(a.charAt(i));}
if(a.charAt(i) == sbr.charAt(sbr.length() -1)) {i++ ;}
else {sbr.append(a.charAt(i));}
}//while
System.out.println("After removing the duplicates => " + sbr);
}//main
}// end1
add a comment |
public String removeAdjDup(Character arr){
int k = 0;
for(int i =0;i<arr.length;i++){
if((i == arr.length-1) && (arr[i] != arr[i-1])){
arr[k] = arr[i];
}
else if(arr[i] == arr[i+1]) continue;
else if((i > 0) && (arr[i] == arr[i-1])) continue;
else if((k > 0) && (arr[i] == arr[k-1])) k = k-1;
else{
arr[k++] = arr[i];
}
}
arr[k] = '';
return Arrays.toString(arr);
}
New contributor
Please see How do I write a good answer?: alternate [solutions] with no explanation or justification do not constitute valid Code Review answers.
– greybeard
7 mins ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f43569%2fremove-all-adjacent-duplicates%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
The problem is not that StringBuilder.deleteCharAt()
is O(n) — you only ever use it to strip the last character. Rather, it's your builder.toString()
that is problematic. It's an O(n) operation that is invoked in a loop up to n times.
Rather than using a StringBuilder
, I recommend manipulating a char
array directly. The problem, as you pointed out, is that By doing your own accounting, you can just build the string correctly the first time.StringBuilder.deleteCharAt(i)
is O(n) because it shifts the rest of the string over.
public static String removeDuplicates(String s) {
if (s.isEmpty()) {
return s;
}
char buf = s.toCharArray();
char lastchar = buf[0];
// i: index of input char
// o: index of output char
int o = 1;
for (int i = 1; i < buf.length; i++) {
if (o > 0 && buf[i] == buf[o - 1]) {
lastchar = buf[o - 1];
while (o > 0 && buf[o - 1] == lastchar) {
o--;
}
} else if (buf[i] == lastchar) {
// Don't copy to output
} else {
buf[o++] = buf[i];
}
}
return new String(buf, 0, o);
}
add a comment |
The problem is not that StringBuilder.deleteCharAt()
is O(n) — you only ever use it to strip the last character. Rather, it's your builder.toString()
that is problematic. It's an O(n) operation that is invoked in a loop up to n times.
Rather than using a StringBuilder
, I recommend manipulating a char
array directly. The problem, as you pointed out, is that By doing your own accounting, you can just build the string correctly the first time.StringBuilder.deleteCharAt(i)
is O(n) because it shifts the rest of the string over.
public static String removeDuplicates(String s) {
if (s.isEmpty()) {
return s;
}
char buf = s.toCharArray();
char lastchar = buf[0];
// i: index of input char
// o: index of output char
int o = 1;
for (int i = 1; i < buf.length; i++) {
if (o > 0 && buf[i] == buf[o - 1]) {
lastchar = buf[o - 1];
while (o > 0 && buf[o - 1] == lastchar) {
o--;
}
} else if (buf[i] == lastchar) {
// Don't copy to output
} else {
buf[o++] = buf[i];
}
}
return new String(buf, 0, o);
}
add a comment |
The problem is not that StringBuilder.deleteCharAt()
is O(n) — you only ever use it to strip the last character. Rather, it's your builder.toString()
that is problematic. It's an O(n) operation that is invoked in a loop up to n times.
Rather than using a StringBuilder
, I recommend manipulating a char
array directly. The problem, as you pointed out, is that By doing your own accounting, you can just build the string correctly the first time.StringBuilder.deleteCharAt(i)
is O(n) because it shifts the rest of the string over.
public static String removeDuplicates(String s) {
if (s.isEmpty()) {
return s;
}
char buf = s.toCharArray();
char lastchar = buf[0];
// i: index of input char
// o: index of output char
int o = 1;
for (int i = 1; i < buf.length; i++) {
if (o > 0 && buf[i] == buf[o - 1]) {
lastchar = buf[o - 1];
while (o > 0 && buf[o - 1] == lastchar) {
o--;
}
} else if (buf[i] == lastchar) {
// Don't copy to output
} else {
buf[o++] = buf[i];
}
}
return new String(buf, 0, o);
}
The problem is not that StringBuilder.deleteCharAt()
is O(n) — you only ever use it to strip the last character. Rather, it's your builder.toString()
that is problematic. It's an O(n) operation that is invoked in a loop up to n times.
Rather than using a StringBuilder
, I recommend manipulating a char
array directly. The problem, as you pointed out, is that By doing your own accounting, you can just build the string correctly the first time.StringBuilder.deleteCharAt(i)
is O(n) because it shifts the rest of the string over.
public static String removeDuplicates(String s) {
if (s.isEmpty()) {
return s;
}
char buf = s.toCharArray();
char lastchar = buf[0];
// i: index of input char
// o: index of output char
int o = 1;
for (int i = 1; i < buf.length; i++) {
if (o > 0 && buf[i] == buf[o - 1]) {
lastchar = buf[o - 1];
while (o > 0 && buf[o - 1] == lastchar) {
o--;
}
} else if (buf[i] == lastchar) {
// Don't copy to output
} else {
buf[o++] = buf[i];
}
}
return new String(buf, 0, o);
}
edited Mar 7 '14 at 1:48
answered Mar 6 '14 at 5:55
200_success
128k15150412
128k15150412
add a comment |
add a comment |
General
Your code formatting is all over the place. You should use consistent and structured indentation. See the Java Code-Style guide for, well, guidance.
if I take your code, and re-format it (Eclipse, CtrlA and CtrlshiftF), it looks like:
public static String removeDuplicate(String s) {
StringBuilder builder = new StringBuilder();
char lastchar = '';
for (int i = 0; i < s.length(); i++) {
String str = builder.toString();
if (!str.equals("") && (str.charAt(str.length() - 1) == s.charAt(i))) {
builder.deleteCharAt(str.length() - 1);
} else if (s.charAt(i) != lastchar)
builder.append(s.charAt(i));
lastchar = s.charAt(i);
}
return builder.toString();
}
At least this allows us to see what you are doing.
Algorithm
A nice algorithm will take data from the input string, and add it to the output if it should be added. A system where you do multiple conversions, add things, and remove things, is complicated, and hard to follow.
Additionally, the null character is actually a valid character in Java, so you may have (an extremely rare) bug.
I do not like that your code is removing all the duplicate values, it seems more practical to remove all but one of the duplicates, but you do not explain why it is supposed to be this way.
More Information required
The above, in itself, is a review, but, if you update your question with the requested details:
- recursion yes/no/why?
- dedup all, or all-but-one?
then I can add suggestions as to how to solve this in a more efficient way.
Actually I had issue while posting the code here, thats why formatting is all over the place. Anyways I follow Google style sheet in my eclipse, so it will be all right.
– AnujKu
Mar 6 '14 at 1:10
The question was : to remove adjacent duplicates from the code. I will post the valid inputs outputs in the question
– AnujKu
Mar 6 '14 at 1:11
add a comment |
General
Your code formatting is all over the place. You should use consistent and structured indentation. See the Java Code-Style guide for, well, guidance.
if I take your code, and re-format it (Eclipse, CtrlA and CtrlshiftF), it looks like:
public static String removeDuplicate(String s) {
StringBuilder builder = new StringBuilder();
char lastchar = '';
for (int i = 0; i < s.length(); i++) {
String str = builder.toString();
if (!str.equals("") && (str.charAt(str.length() - 1) == s.charAt(i))) {
builder.deleteCharAt(str.length() - 1);
} else if (s.charAt(i) != lastchar)
builder.append(s.charAt(i));
lastchar = s.charAt(i);
}
return builder.toString();
}
At least this allows us to see what you are doing.
Algorithm
A nice algorithm will take data from the input string, and add it to the output if it should be added. A system where you do multiple conversions, add things, and remove things, is complicated, and hard to follow.
Additionally, the null character is actually a valid character in Java, so you may have (an extremely rare) bug.
I do not like that your code is removing all the duplicate values, it seems more practical to remove all but one of the duplicates, but you do not explain why it is supposed to be this way.
More Information required
The above, in itself, is a review, but, if you update your question with the requested details:
- recursion yes/no/why?
- dedup all, or all-but-one?
then I can add suggestions as to how to solve this in a more efficient way.
Actually I had issue while posting the code here, thats why formatting is all over the place. Anyways I follow Google style sheet in my eclipse, so it will be all right.
– AnujKu
Mar 6 '14 at 1:10
The question was : to remove adjacent duplicates from the code. I will post the valid inputs outputs in the question
– AnujKu
Mar 6 '14 at 1:11
add a comment |
General
Your code formatting is all over the place. You should use consistent and structured indentation. See the Java Code-Style guide for, well, guidance.
if I take your code, and re-format it (Eclipse, CtrlA and CtrlshiftF), it looks like:
public static String removeDuplicate(String s) {
StringBuilder builder = new StringBuilder();
char lastchar = '';
for (int i = 0; i < s.length(); i++) {
String str = builder.toString();
if (!str.equals("") && (str.charAt(str.length() - 1) == s.charAt(i))) {
builder.deleteCharAt(str.length() - 1);
} else if (s.charAt(i) != lastchar)
builder.append(s.charAt(i));
lastchar = s.charAt(i);
}
return builder.toString();
}
At least this allows us to see what you are doing.
Algorithm
A nice algorithm will take data from the input string, and add it to the output if it should be added. A system where you do multiple conversions, add things, and remove things, is complicated, and hard to follow.
Additionally, the null character is actually a valid character in Java, so you may have (an extremely rare) bug.
I do not like that your code is removing all the duplicate values, it seems more practical to remove all but one of the duplicates, but you do not explain why it is supposed to be this way.
More Information required
The above, in itself, is a review, but, if you update your question with the requested details:
- recursion yes/no/why?
- dedup all, or all-but-one?
then I can add suggestions as to how to solve this in a more efficient way.
General
Your code formatting is all over the place. You should use consistent and structured indentation. See the Java Code-Style guide for, well, guidance.
if I take your code, and re-format it (Eclipse, CtrlA and CtrlshiftF), it looks like:
public static String removeDuplicate(String s) {
StringBuilder builder = new StringBuilder();
char lastchar = '';
for (int i = 0; i < s.length(); i++) {
String str = builder.toString();
if (!str.equals("") && (str.charAt(str.length() - 1) == s.charAt(i))) {
builder.deleteCharAt(str.length() - 1);
} else if (s.charAt(i) != lastchar)
builder.append(s.charAt(i));
lastchar = s.charAt(i);
}
return builder.toString();
}
At least this allows us to see what you are doing.
Algorithm
A nice algorithm will take data from the input string, and add it to the output if it should be added. A system where you do multiple conversions, add things, and remove things, is complicated, and hard to follow.
Additionally, the null character is actually a valid character in Java, so you may have (an extremely rare) bug.
I do not like that your code is removing all the duplicate values, it seems more practical to remove all but one of the duplicates, but you do not explain why it is supposed to be this way.
More Information required
The above, in itself, is a review, but, if you update your question with the requested details:
- recursion yes/no/why?
- dedup all, or all-but-one?
then I can add suggestions as to how to solve this in a more efficient way.
edited Mar 6 '14 at 1:06
answered Mar 6 '14 at 1:00
rolfl♦
90.7k13190394
90.7k13190394
Actually I had issue while posting the code here, thats why formatting is all over the place. Anyways I follow Google style sheet in my eclipse, so it will be all right.
– AnujKu
Mar 6 '14 at 1:10
The question was : to remove adjacent duplicates from the code. I will post the valid inputs outputs in the question
– AnujKu
Mar 6 '14 at 1:11
add a comment |
Actually I had issue while posting the code here, thats why formatting is all over the place. Anyways I follow Google style sheet in my eclipse, so it will be all right.
– AnujKu
Mar 6 '14 at 1:10
The question was : to remove adjacent duplicates from the code. I will post the valid inputs outputs in the question
– AnujKu
Mar 6 '14 at 1:11
Actually I had issue while posting the code here, thats why formatting is all over the place. Anyways I follow Google style sheet in my eclipse, so it will be all right.
– AnujKu
Mar 6 '14 at 1:10
Actually I had issue while posting the code here, thats why formatting is all over the place. Anyways I follow Google style sheet in my eclipse, so it will be all right.
– AnujKu
Mar 6 '14 at 1:10
The question was : to remove adjacent duplicates from the code. I will post the valid inputs outputs in the question
– AnujKu
Mar 6 '14 at 1:11
The question was : to remove adjacent duplicates from the code. I will post the valid inputs outputs in the question
– AnujKu
Mar 6 '14 at 1:11
add a comment |
Ultimately you have to remove the duplicates from the String without using HashSet. One technique is to sort the char array first. The complete code is:
public class Test3 {
public static void main(String args) {
String str = "ABBCDAABBBBBBBBOR";
char ca = str.toCharArray();
Arrays.sort(ca);
String a = new String(ca);
System.out.println("original => " + a);
int i = 0 ;
StringBuffer sbr = new StringBuffer();
while(i < a.length()) {
if(sbr.length() == 0 ) {sbr.append(a.charAt(i));}
if(a.charAt(i) == sbr.charAt(sbr.length() -1)) {i++ ;}
else {sbr.append(a.charAt(i));}
}//while
System.out.println("After removing the duplicates => " + sbr);
}//main
}// end1
add a comment |
Ultimately you have to remove the duplicates from the String without using HashSet. One technique is to sort the char array first. The complete code is:
public class Test3 {
public static void main(String args) {
String str = "ABBCDAABBBBBBBBOR";
char ca = str.toCharArray();
Arrays.sort(ca);
String a = new String(ca);
System.out.println("original => " + a);
int i = 0 ;
StringBuffer sbr = new StringBuffer();
while(i < a.length()) {
if(sbr.length() == 0 ) {sbr.append(a.charAt(i));}
if(a.charAt(i) == sbr.charAt(sbr.length() -1)) {i++ ;}
else {sbr.append(a.charAt(i));}
}//while
System.out.println("After removing the duplicates => " + sbr);
}//main
}// end1
add a comment |
Ultimately you have to remove the duplicates from the String without using HashSet. One technique is to sort the char array first. The complete code is:
public class Test3 {
public static void main(String args) {
String str = "ABBCDAABBBBBBBBOR";
char ca = str.toCharArray();
Arrays.sort(ca);
String a = new String(ca);
System.out.println("original => " + a);
int i = 0 ;
StringBuffer sbr = new StringBuffer();
while(i < a.length()) {
if(sbr.length() == 0 ) {sbr.append(a.charAt(i));}
if(a.charAt(i) == sbr.charAt(sbr.length() -1)) {i++ ;}
else {sbr.append(a.charAt(i));}
}//while
System.out.println("After removing the duplicates => " + sbr);
}//main
}// end1
Ultimately you have to remove the duplicates from the String without using HashSet. One technique is to sort the char array first. The complete code is:
public class Test3 {
public static void main(String args) {
String str = "ABBCDAABBBBBBBBOR";
char ca = str.toCharArray();
Arrays.sort(ca);
String a = new String(ca);
System.out.println("original => " + a);
int i = 0 ;
StringBuffer sbr = new StringBuffer();
while(i < a.length()) {
if(sbr.length() == 0 ) {sbr.append(a.charAt(i));}
if(a.charAt(i) == sbr.charAt(sbr.length() -1)) {i++ ;}
else {sbr.append(a.charAt(i));}
}//while
System.out.println("After removing the duplicates => " + sbr);
}//main
}// end1
edited Apr 21 at 6:11
answered Apr 20 at 19:45
Soudipta Dutta
92
92
add a comment |
add a comment |
public String removeAdjDup(Character arr){
int k = 0;
for(int i =0;i<arr.length;i++){
if((i == arr.length-1) && (arr[i] != arr[i-1])){
arr[k] = arr[i];
}
else if(arr[i] == arr[i+1]) continue;
else if((i > 0) && (arr[i] == arr[i-1])) continue;
else if((k > 0) && (arr[i] == arr[k-1])) k = k-1;
else{
arr[k++] = arr[i];
}
}
arr[k] = '';
return Arrays.toString(arr);
}
New contributor
Please see How do I write a good answer?: alternate [solutions] with no explanation or justification do not constitute valid Code Review answers.
– greybeard
7 mins ago
add a comment |
public String removeAdjDup(Character arr){
int k = 0;
for(int i =0;i<arr.length;i++){
if((i == arr.length-1) && (arr[i] != arr[i-1])){
arr[k] = arr[i];
}
else if(arr[i] == arr[i+1]) continue;
else if((i > 0) && (arr[i] == arr[i-1])) continue;
else if((k > 0) && (arr[i] == arr[k-1])) k = k-1;
else{
arr[k++] = arr[i];
}
}
arr[k] = '';
return Arrays.toString(arr);
}
New contributor
Please see How do I write a good answer?: alternate [solutions] with no explanation or justification do not constitute valid Code Review answers.
– greybeard
7 mins ago
add a comment |
public String removeAdjDup(Character arr){
int k = 0;
for(int i =0;i<arr.length;i++){
if((i == arr.length-1) && (arr[i] != arr[i-1])){
arr[k] = arr[i];
}
else if(arr[i] == arr[i+1]) continue;
else if((i > 0) && (arr[i] == arr[i-1])) continue;
else if((k > 0) && (arr[i] == arr[k-1])) k = k-1;
else{
arr[k++] = arr[i];
}
}
arr[k] = '';
return Arrays.toString(arr);
}
New contributor
public String removeAdjDup(Character arr){
int k = 0;
for(int i =0;i<arr.length;i++){
if((i == arr.length-1) && (arr[i] != arr[i-1])){
arr[k] = arr[i];
}
else if(arr[i] == arr[i+1]) continue;
else if((i > 0) && (arr[i] == arr[i-1])) continue;
else if((k > 0) && (arr[i] == arr[k-1])) k = k-1;
else{
arr[k++] = arr[i];
}
}
arr[k] = '';
return Arrays.toString(arr);
}
New contributor
edited 13 mins ago
New contributor
answered 29 mins ago
Surekha Kuruba
11
11
New contributor
New contributor
Please see How do I write a good answer?: alternate [solutions] with no explanation or justification do not constitute valid Code Review answers.
– greybeard
7 mins ago
add a comment |
Please see How do I write a good answer?: alternate [solutions] with no explanation or justification do not constitute valid Code Review answers.
– greybeard
7 mins ago
Please see How do I write a good answer?: alternate [solutions] with no explanation or justification do not constitute valid Code Review answers.
– greybeard
7 mins ago
Please see How do I write a good answer?: alternate [solutions] with no explanation or justification do not constitute valid Code Review answers.
– greybeard
7 mins ago
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f43569%2fremove-all-adjacent-duplicates%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
6
Why does it have to be recursive? ... and if it has to be recursive, why is your code not recursive?
– rolfl♦
Mar 6 '14 at 0:31
1
Additionally, what does it mean to remove duplicates? If I give your code the word
messy
it returnsmey
... I was expectingmesy
... which one is right? Why?– rolfl♦
Mar 6 '14 at 0:34
@rolfl The examples added in Rev 2 clarify both issues.
"messy"
→"mey"
. "Recursively remove" refers to the problem statement, not the implementation.– 200_success
Mar 6 '14 at 5:58