Array ( [0] => [1] => questions [2] => Strings [3] => Remove-adjacent-duplicates ) Strings | Remove adjacent duplicates | THE INQUISITIVE






Remove adjacent duplicates

LEVEL:Beginner

Description

Given a string K. You have to remove all the adjacent duplicate values in given string.

Input Format

First line contains the string K.

Output Format

Print the string after removing adjacent duplicates.


Example 1:

Input
abaa
Output
aba
Example 2:

Input
abbaa
Output
aba
Example 3:

Input
abcd
Output
abcd

oops

Login to see Discussion




Approach

Approach 1: using two loops

step-i) convert given string to character array as strings are immutable
step-ii) get the length of the string
step-iii)assign 0 to i
step-iv) check if character at index i and index i+1 are same or not
step-v) if same move all the elements to left by one postion and decrement the length by one value
step-vi)increment i value by one
step-vii) repeat steps iv to vi still i is less than the value of length
step-step-viii) create a empty string answer and concatinat all the characters of the array to it
step-ix) return answer

Time Complexity: O(n^2)
Space Complexity: O(n)

Approach and Analysis:

step-i) convert given string to character array
step-step-step-ii)assign null to prev which is character
step-step-iii)assign 0 to k which is a integer
step-iv) traverse the character array and check if adjacent elements are same or not
step-v)if they are not same append that character to the array increment k value and assign that character to prev
step-vi) convert that character array to string
step-vii)return the substring of the converted string from 0 to k

Time Complexity: O(n)
Space Complexity: O(n)


Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

oops

Login to see Solution






     Recommended Questions      

Topic: Strings

Beginner

1. Timing Format2. Date Format3. Palindrome 4. Anagrams5. Balanced Parenthesis6. Equal Strings7. Smallest Window8. Reverse of String9. Distinct Palindromes10. Remove adjacent duplicates11. Run length encoding12. Non repeating Character13. Array of strings14. Find Excel Column15. Transform one string to another16. Move Robot in circular17. Zig Zag concatenation. 18. Min No of elements19. Combination of strings used to dial a number20. Ancient String