The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Arrays & Strings

Problem :-
Remove all the duplicate characters in a string.

Solution :-
We will use the hash map technique here.
Create a hash_map[26] ( 26 for the alphabet set) and initialize all indices to 0.
While traversing the array, if we see a character 'x', set hash_map[x] = 1.
If we see 'x' next time, we will not consider that element in the array.

#include<iostream>
using namespace std;

// remove the duplicate characters from the string
// function is case insensitive
// i.e 'a' and 'A' are duplicates
void removeDuplicateChars(char str[],int size) {
   int hash_map[26] = {0};
   int i;
   int pos = 0;
   for (i=0;i<size;i++) {
      // get the ascii value of the character
      int val = ((str[i] > 96) ? str[i]-'A'-32 : str[i]-'A');
      if (hash_map[val] == 0) {
         //character not seen previously
         str[pos] = str[i];
         pos++;
         hash_map[val] = 1;
      }
   }
   str[pos] = 0; // end the string
}

// main
int main() {
   char str[] = "thisIsastring";
   int size = sizeof(str);
   cout<<"\nOriginal String :: "<<str;
   removeDuplicateChars(str,size);
   cout<<"\nAfter removing duplicate Characters :: "<<str;
   cout<<endl;
}

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j - i ) s.t arr(j) > arr(i)