CareerCup

This can be resolved using a simple approach - no hashmaps. You can reduce your complexity to O(N) by simply using an array of size 128 characters (to represent ASCII values). This boolean array will track the characters you encounter as you iterate through the string.

Implementation below:

String removeDuplicates(String str) {
	StringBuilder sb = new StringBuilder();
	boolean[] char_set = new boolean[128];
		
	for (int i = 0; i < str.length(); i++) {
		int c = str.charAt(i);
		if (!char_set[c]) {
			sb.append((char)c);
			char_set[c] = true;
		}
	}
	return sb.toString();
}

Hey guys, I think it would be simplest just to use a HASHSET.
With the if statement we try to add the current character to the hash set; if we succeed, it means that the char is encountered for the first time, so we increment the counter i, otherwise (when if returns false), we just remove the particular char. Note that the value of i is not incremented.

Hope it helps. :)

public static String cocoBee(String str){
		
		StringBuilder sb = new StringBuilder(str);
		HashSet<Character> hs = new HashSet<>();
		
		for(int i = 0; i < sb.length(); ){
			
			
			if(hs.add(sb.charAt(i))){
				i++;
			}
			else{
				sb.deleteCharAt(i);
			}
			
		}
		return sb.toString();
	}

public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner scanner = new Scanner(System.in);
		String str = scanner.next();
		String str2 = cocoBee(str);
		
		System.out.println(str2);

	}

I think the question is about removing duplicate characters from the string. For example: If the string is "amazon", the output should be "amzon".
This can be done in O(N) using a HashMap.
Algorithm:
1. Traverse the string character by character
2. Enter the character in the HashMap<Character, Boolean> as key if it is not already present
3. If a character is already in HashMap, we found a duplicate.
4. Based on the requirement, we can either just display the characters and skip the duplicate characters OR store the characters in a character array and return the resultant array as a String.

Remove duplicates from string..does that mean

abaaabbcdeee = abcd or = ababcde ?

If its second then its easy to do in O(n)

If the characters are s8 bits, you can use a 256 size boolean array as your O(1) space hashmap for an O(n) time algorithm.

I think it formated my white space automatically while posting

If your string is "     Hello      World   "
Your output should be "Hello World"

Sorry I posted to the wrong question. The one I posted is to remove duplicate white spaces in specific from a string

String is an immutable object. "in place" modification does not make sense to me

eewe

O(N) algorithm: Keep count of number of spaces an unique character has to left shifted. Start with 0. Create hash map of 127 values
For each character,
1. If it is not yet seen, move it left by count. Add to hash map.
2. If it is duplicate, increment count.

I think using hash or boolean array voilates in place as it uses too much extra memory. Instead of using a boolean array, use a int variable and set its bits according to the Ascii value of the char you encounter. So you only very little extra space and hence it doesnt voilates inplace!

I faced the same question in the interview. I think what the meant was this

The array AMAZON would become AMZON\n. Just add a special character at the end to specify that you would have your result before that. In this case you just cant erase a string you have to copy the char 'Z' at index 2 and shift all the remaining characters by one.

This problem is little more involved than simple removal of duplicates.

Assuming that string contain ASCII chars (array can be extended to 256 for extended ASCII), below solution in Java will take O(n) time:

public static String removeDupChars(String input) {
		if(input==null || input.length() == 0) {
			return input;
		}
		String newStr = "";
		int[] charSet = new int[128];
		for(char c : input.toCharArray()) {
			if(charSet[c] == 0) {
				newStr = newStr + c;
			}
			charSet[c]++;
		}
		return newStr;
	}

Idea to do it inplace is to swap the dupes to the end of the array and maintain a variable that tells you end of the unique values , result will be char [] from 0 to end. See code below :-

Note : string builder is just a syntactical sugar , we already have result in input array from 0 to end

public static string RemoveDupesInPlace(this string input)
        {
            bool[] present = new bool[255];
            int end = input.Length - 1;
            char temp;
            char[] inputArray = input.ToArray<char>();
            StringBuilder builder = new StringBuilder();

            for (int i = 0; i < inputArray.Length && i < end; i++)
            {
                if (present[inputArray[i] - 'a'])
                {
                    temp = inputArray[end];
                    inputArray[end] = inputArray[i];
                    inputArray[i] = temp;
                    end--;
                    i--;
                }
                else
                {
                    present[inputArray[i] - 'a'] = true;
                }
            }

            foreach (var item in inputArray.Take(end))
            {
                builder.Append(item);
            }

            return builder.ToString();

}

public static char[] removeDups(char []dups) {

        int i = 0;

        for(int j = 1; j < dups.length;j++) {
            boolean flag = false;

            for(int k = 0;k <= i; k++) {
                if(dups[k] == dups[j]) {
                    flag = true;
                    break;
                }
            }

            if(flag == false) {
                i++;
                dups[i] = dups[j];
            }
        }

        return Arrays.copyOf(dups,i + 1);
    }

class RemoveDup(
    val str: String) {

    def removedup(): String = {
        val a = new Array[Boolean](256)
        val sb = new StringBuffer
        str.foreach(c => {
            if (a(c.toInt) == false) {
              a(c.toInt) = true
              sb.append(c)
            }
        })
        sb.toString
    }
}

object RemoveDup {
    def main(args: Array[String]):Unit = {
        val inst = new RemoveDup("amazon")
        val after: String = inst.removedup
        println(after)
    }
}

use hashset and hashset buffer.
just check if the element is present in the hashset
if present{
put the element in to hashset
}
else
dont put.

/* assume ASCII */
int remove_duplicates(char *str)
{
    char *cp, *currentp;
    unsigned char map[32] = {0};

    for (currentp = str, cp = str; *cp; cp++)
    {
        if (!(map[*cp >> 3] & ( 1 << (*cp & 7))))
        {
            map[*cp >> 3] |= (1 << (*cp & 7));
            *currentp++ = *cp;
        }        
    }

    *currentp = '\0';

    return currentp - str;
}

i am just going to help you out with logic:

first take the string in a variable

secondly use a loop construct to loop until the stringlength

use an if clause and compare the string character by character

if the character repeats two times go for else clause and increment the array of characters by +1 (this step eliminates the dual characters)

similarly for all
characters in an array and then print the array it display the series of character without duplicates .

Thus you can achieve it.
NOTE: take string as array of character as you take in C-lang.

Hope it was useful.
Thank U.-

boolean check =false; //"";
		 
		 String word = "Hello World";
		 HashSet<Character>s = new HashSet<Character>();
		
		 String result = "";
		 for(int i = 0 ; i < word.length();++i)
		 {
			 check =s.add(word.charAt(i));
			 if(check==true)
			 {
				 result += word.charAt(i);
			 }
		 }
		 System.out.println(result);

public static String dup(String word)
	{
 boolean check =false; //"";
		 
		 HashSet<Character>s = new HashSet<Character>();
		
		 String result = "";
		 for(int i = 0 ; i < word.length();++i)
		 {
			 check =s.add(word.charAt(i));
			
			  if(word.charAt(i)>='a'&&word.charAt(i)<='z')
			 {
				 char ch =  (char)((char)word.charAt(i)-'a'+'A');
				 check =s.add(ch);
				 if(check==true)
				 {
					 result += word.charAt(i);
				 }
			 }
			 else if(word.charAt(i)>='A'&&word.charAt(i)<='Z')
			 {
				 char ch =  (char)((char)word.charAt(i)-'A'+'a');
				 check =s.add(ch);
				 if(check==true)
				 {
					 result += word.charAt(i);
				 }
				 
			 }
			 else
			 {
				 if(check==true)
				 {
					 result += word.charAt(i);
				 }
			 }
			 
		 }
		 return result;
}

O(n)

void rmDup(string &str) {
   set<char> s;
   for (int i = 0; i < str.size(); i++) {
       if (s.find(str[i]) == s.end()) {
           s.insert(str[i]);
       } else {
           str.erase(i,1);
       }
   }
}

StringBuilder myNewString = new StringBuilder();
                for (int i = 0; i < str.Length; i++)
                {
                    if (i == 0 && str[i] == ' ')
                        continue;
                    if (i == str.Length - 1 && str[i] == ' ')
                        continue;
                    if (i > 0)
                    {
                        if (str[i] == ' ' && str[i - 1] == ' ')
                            continue;
                        else
                        {
                            
                            myNewString.Append(str[i]);
                        }
                    }
                }
                return myNewString.ToString();

suppose your string is " Hello World "
your output should be "Hello World"

I think it is nor possible to do it in O(n) time complexity without extra space. In order to remove duplicates we have to keep track of elements which have been already processed or time complexity will be bigger cause multiple check of the same elements is required.