Google Interview Question for Software Developers


Country: -
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
8
of 8 vote

UPD: I could find a way to optimize my code to O(N). Main idea is the same. I added updated part after my old explanations


Here's my O(N^2) idea which is absoloutly true:D ( proved, and tested with many random test cases)

Let's say we have string S:

I define next[i] = next position (after i) which is equal to S[i], if there is not, -1.

So if S="bacdbcb", next={4,-1,5,-1,6,-1,-1}

Now, I iterate through S, from left to right, and at each position, I decide whether to pick the current character or not. Also, there is an array called visited, which visited[i]=true means character i has been picked.

Greedy part:
If we are at position i, (let's say x=S[i]), we need to find the first j>i which next[j]=-1 and visited[j]=false, call it y=S[j]. Also I need to know what is the smallest character from i to j, call it z( and obviously visited[z]=false). If the smallest character in between, z, is bigger than x, then add x to answer and visited[x] = true, otherwise skip x and continue to i+1.

Here's the reason:
We have something like this.
....x .... z ... y ...
It means definietly y is the part of answer string (since its next is -1). So if there is nothing smaller than x between x and y (including y), for sure it's better to choose x to have a smaller lexicographic answer.(note that all the characters between x and y have another copy after y, since y is the first position which has no next, so it's safe to postpone picking them, if needed). On the other hand, if z<x for sure it's better to skip x and choose another x later on.

Because at each position i, we need to see, in worst case, all next characters, so time complexity is O(N^2).

I couldn't find a way to find y in O(logn) or O(1), if there is any suggestion please let me know.

Also, I really really enjoyed the problem and it took me a day to come up with this solution!

string removeRepeated(string s)
{
	int N=s.size();
	vector<int> next(N);
	int lastPos[26];
	for (int i=0;i<26;i++)
		lastPos[i]=-1;

	for (int i=N-1;i>=0;i--){
		int ind = s[i]-'a';
		next[i] = lastPos[ind];
		lastPos[ind]=i;
	}
	
	vector<bool> visited(26,false);
	string ans;
	for (int i=0;i<N;i++){
		int cur = s[i]-'a';

		if (visited[cur]) continue;
		if (next[i]==-1){
			ans+=s[i];
			visited[cur]=true;
		}
		else{
			
			int j=i+1;
			char smaller=s[i];
			while(j<N){
				if (visited[s[j]-'a']==false){
					smaller = min (smaller , s[j]);
					if (next[j]==-1) break;
				}
				j++;
			}

			if (s[i]<=smaller){
				ans+=s[i];
				visited[cur]=true;
			}
		}
	}

	return ans;
}

UPD: As I said it seemed it's possible to find y better than visiting all next characters.Using a stack I optimized the solution to O(26*N) = O(N)

for each character, I add all of its positions in the string, into a stack.(from right to left of S)
Also I keep the last position of each character in lastPos array.

After processing a character from position i, I pop its position from its stack. So when I'm at position i, each element of all stacks are greater than i.(all positions before i are popped beforehand from their stacks).


Now, I can find y and z much faster.
position of y = min (lastPos[k]), which k is all characters which are not visited yet.
Is there any z<x = if there is a character smaller than x which top of its stack is less than position of y.

So time complexity is 26*N or O(N).

Here's the code:

string removeRepeatedLinear(string s)
{
	int N=s.size();
	stack<int> pos[26];//positions of each character
	int lastPos[26]={-1};

	for (int i=N-1;i>=0;i--){
		int cur= s[i]-'a';
		if (pos[cur].empty())
			lastPos[cur]=i;

		pos[cur].push(i);
	}


	vector<bool> visited(26,false);
	string ans;
	for (int i=0;i<N;i++){
		int cur = s[i]-'a';

		if (visited[cur]) continue;
		if (pos[cur].size()==1){ //last character of cur
			ans+=s[i];
			visited[cur]=true;
		}
		else{
			bool isSmaller=false;
			int minpos=N;
			for (int k=0;k<26;k++){
				if (!visited[k] && !pos[k].empty())
					minpos=min(minpos,lastPos[k]);
			}

			for (int k=0;k<cur && !isSmaller;k++){
				if (visited[k] || pos[k].empty()) continue;
				if (pos[k].top()<=minpos)
					isSmaller=true;
			}

			if (isSmaller==false){
				ans+=s[i];
				visited[cur]=true;
			}
		}

		pos[cur].pop();
	}

	return ans;
}

- MehrdadAP September 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

magic, it works

- manzhos.max September 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Really nice solution. I can't imagine coming up with it in 30 minutes.

One minor improvement would be to break your loop over j when s[j] < s[i]. You don't need the minimum for anything except comparing with s[i]. This won't change the worst case, but will save a few iterations of that inner loop in some cases.

- andrew September 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@andrew, you're right. It could be applied and make it faster.
I'll update the code.
Thanks :)

- MehrdadAP September 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yaay! Finally I could optimize the solution to linear time... So happy :D

- MehrdadAP September 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is really cool ! Thanks a lot!

- lxfuhuo September 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How are you removing c from bacdbcb?

- ajit@ajitk.in September 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ajit, the next character after first c which has no next is d. Also, between c and d there is no smaller character than c. so first c will be picked.

- MehrdadAP September 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Try lmznopnbdfikmonqsvnlmznop, which generates bdfikmnqsvlzop. The o at the end would be better placed between the m and the n. It took me a while to tell that next had an index of the string and lastPos had the index of the letter (I thought both had the letter index). Technically, lastPos might better be a bool, as you never read the value.

- username12312312 December 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my answer, the only thing you need to understand before starting is what lexicographical order is, and how it works.
This function traverses the string twice, so, is O(2*n) = O(n). The first time we check if an specific letter has been found before, if it has been found then selected the position with less weight, for example:
abcd = 0(10^3) + 1(10^2) + 2(10^1) + 3(10^0) = 123
or
bcda = 1(10^3) + 2(10^2) + 3(10^1) + 0(10^0) = 1230
because 123 < 1230 we select the first position.
Once you have all position with the less weight you can compose the final string only picking the character using your position array.
Just traversing twice.

char * lexicoGraphicalOrderCompression (char * string) {
    size_t size = strlen(string);
    int chart[26]; // only lowercase
    std::fill(chart, chart + 26, -1); // init buffer with known value
    
    int weight=0;
    for (int i=0; i<size; i++) {
        int value = string[i]-'a';
        int position = chart[value];
        if (position < 0) {
            chart[value] = i; // set initial position
        } else {
            // another position for the same character has been found
            int temp = weight*10 + value;
            int k = i - position;
            temp = pow(10,k-1)*((temp / int(pow(10,k))) - value) + temp%int(value * pow(10,k));
            
            // if the weight for the current position is less than the previous one, then update position in buffer
            if (temp < weight) {
                chart[value] = i;
            }
        }
        weight = weight*10 + value;
    }
    
    // compose final string
    int j=0;
    for (int i=0; i<size; i++) {
        int value = string[i]-'a';
        if (chart[value] == i){
            string[j++] = string[i];
        }
    }
    string[j] = '\0';
    return string;
}

- byPaco September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the string contains 26 characters, the integer will overflow.

- lxfuhuo September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved in O(n) memory and O(n) time.

The following solution takes O(n^2) time. I will then explain the optimizations.

Idea: Iterate through the string, for every char lets say at position i

1. find the the first character(not already included) smaller than str[i] in str[i+1,n] at some position j. If no char exists, include s[i]
2. If exists, check if the substring j to n contains all the distinct characters not included till now.
3. if it does, leave char at position i, else take it.
Eg: cbacdcbc
included -> { }
i = 1, c
j = 2, b: bacdcbc contains all chars, leave c

i = 2, b
j = 3, a: acdcbc contains all chars, leave b

i = 3, a
j = NONE: take a included = {a}

i = 4, c
j = 7, b: bc doesnt contain d, take c, included {ac}

and so on.

CODE
note: Ignore the log(n) factor because of SET as that can be done using an array as well

#include<bits/stdc++.h>
using namespace std;

int main()
{
    while(1)
    {   string str;
        cin>>str;
        int n = str.length();
        string ans;
        vector<bool> included(256,0);
        set<char> distinct;
        for(int i = 0 ; i < n ; i++)
        {
            distinct.insert(str[i]);
        }
        int nd = distinct.size();
        for(int i = 0 ; i < n ; i++)
        {
            if(included[str[i]])
                continue;
            int nextSmall = -1;
            for(int j = i+1 ; j<n ; j++)
            {
                if(str[j] < str[i])
                {
                    nextSmall = j;
                    break;
                }
            }
            if(nextSmall == -1)
            {
                included[str[i]] = 1;
                ans.push_back(str[i]);
                continue;
            }

            int inc = ans.length();
            set<char> S;
            
            for(int j = nextSmall; j<n ; j++)
            {
                if( !included[ str[j] ] )
                {
                    S.insert(str[j]);
                }
            }
            int d = S.size();
            if(d !=  nd - inc)
            {   
                included[str[i]] = 1;
                ans.push_back(str[i]);
            }
        }
        cout<<ans<<endl;
    }

}

Optimizations:
1. To get the first smaller element on the right to str[i], we can do a preprocessing using a stack giving us a O(1) lookup.
2. To count the number of distincts from j to n, we can use bit masking or some other technique.

- Arpit September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Linear algo on python with some explanations.

class ListNode:
    def __init__(self, idx, prev, next):
        self.idx = idx
        self.prev = prev
        self.next = next


map = {}

links = []
idxToRemove = []

def __remove(idx):
    idxToRemove.append(idx)

    prevNode = links[idx].prev
    nextNode = links[idx].next
    links[prevNode].next = nextNode
    links[nextNode].prev = prevNode

def removeDuplicatedLetters(s):


    for i in range(len(s)):
        links.append(ListNode(i, i - 1, i + 1))

    for idx, c in enumerate(s):
        if not c in map.keys():
            map[c] = []
        map[c].append(idx)

    letterList = filter(lambda x: len(map[x]) > 1, map.keys())
    letterList.sort()
    letterList.reverse()

    for c in letterList:
        candidates = []
        for idx in reversed(map[c]):
            if links[idx].next >= len(s) or s[links[idx].next] <= s[idx]:
                #good candidate to remove
                candidates.append(idx)

        if len(candidates) == 0: # have to remove all except first appearance
            for i in range(1, len(map[c])):
                __remove(map[c][i])

        elif len(candidates) == len(map[c]): # have to remove all entries except last
            for i in range(len(map[c]) - 1):
                __remove(map[c][i])

        else: # have to remove all the candidates + all others except last non-candidate
            positionToSkip = max(filter(lambda x: x not in candidates, map[c]))
            for i in map[c]:
                if i != positionToSkip:
                    __remove(i)

    answer = ""
    for i in range(len(s)):
        if i not in idxToRemove:
            answer += s[i]

    return answer

- art.averin September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringSvc
{
	public String shortestLexicoString(String s)
	{
	//If the string has all unique characters then it is already in shortest lexicographically ordered form.
		HashMap<Character,Boolean> charsFound=new HashMap<Character,Boolean>();
		boolean isUnique=true;
		for(int i=0;i<s.length() && isUnique;i++)
		{
			if(charsFound.contains(s.charAt(i)))
			{
				isUnique=false;
			}else
			{
				charsFound.put(s.charAt(i),true);
			}
		}
		if(isUnique)
		{
			return s;
		}
		//If the string has duplicate characters, find the smallest lexicographically ordered string with all characters
		String result=""+s.charAt(0);
		char earliest=s.charAt(0);//lexicographically earliest character.
		String curr=""+s.charAt(0);
		HashMap<Character,Boolean> existsInResult=new HashMap<Character,Boolean>();
		existsInResult.put(existsInResult.charAt(0));
		for(int i=1;i<s.length();i++)
		{
			if(s.charAt(i)-earliest>0)//If current character occurs after the earliest character
			{
				if(!existsInResult.contains(s.charAt(i))//If the current character hasn't been added to the curretn string
				{
					curr+=s.charAt(i);//add the character to the string
					existsInResult.put(s.charAt(i),true));
					if(curr.length()>=result.length())//If the length of the current string is greater then or equal to the maximum length string seen so far
					{
						result=curr;
					}
				}
				
				
			}else
			{
				if(s.charAt(i)-earliest<0)//If the current character isn't lexicographically after the earliest character, then it is the new earliest character.
				{
					curr=""+s.charAt(i);//Start a new string
					existsInResult=new HashMap<Character,Boolean>()//Create a new hash map to store characters to be added to the new string.
					earliest=s.charAt(i);//Set earliest character to the current character. 
					existsInResult.put(s.charAt(i),true);//Store current character into hash map.
				}
				
			}
		}
		return result;
		
	}
}

Worst case Time complexity O(n).Space O(n)--assuming input string is all unique characters.

- divm01986 September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the first pass find the last occurrence of each letter. Then make a second pass, building a candidate solution. For each letter c of the input string:

while 
	(1) the last letter c' of the candidate solution so far is larger and 
	(2) the last occurrence of c' is yet to be encountered
    remove c' from the candidate solution.
    add c to the candidate solution

- Irit September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the first pass, find for each character c the last occurrence of c in the input.
In the second pass, build a the solution as follows:

Put the first character of the input in the solution. Then, for each character c of the input:
if c is not already in the solution: let c' be the last character of the solution so far. while (c' > c and last occurrence of c' is yet to be seen) remove c' from the candidate solution. Then put c at the end of the solution.

- Irit September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry about the dupe, I thought the first one got lost. Feel free to delete one.

- Irit September 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can you explian the question more? can you explain more about the order ?

- jigili September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you could get the conception form wiki~

- lxfuhuo September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is What I came up with. It uses two passes and a histogram. The first pass creates the histogram and the second one uses two pointers to walk the string and decide what chars to keep and which to discard using the counts in the histogram.

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char** argv) {
  if (argc < 2) {
    return EXIT_FAILURE;
  }

  int hist[26] = {0};
  char* forwardProbe = argv[1];
  char* rearProbe = forwardProbe;

  while (*forwardProbe) {
    hist[*forwardProbe - 'a']++;
    forwardProbe++;
  }

  forwardProbe = rearProbe;
  while (*forwardProbe) {
    switch (hist[*forwardProbe - 'a']) {
    case 0:
      break;
    case 1:
      *rearProbe = *forwardProbe;
      rearProbe++;
      hist[*forwardProbe - 'a'] = 0;
      break;
    default:
      if (*forwardProbe < *(forwardProbe + 1)
          || (rearProbe == argv[1]? *rearProbe < *forwardProbe
              : *(rearProbe -1) < *forwardProbe) )
        {
          *rearProbe = *forwardProbe;
          rearProbe++;
          hist[*forwardProbe - 'a'] = 0;
      } else {
        hist[*forwardProbe - 'a']--;
      }
      break;
    }
    forwardProbe++;
  }
  *rearProbe = '\0';
  printf("%s\n", argv[1]);
  return EXIT_SUCCESS;
}

- mfalko September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I just realized I posted this twice, I thought the site glitched when I first posted, then I logged in and posted again. Can this be deleted?

- mfalko September 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is what I was able to come up with. I wanted to keep it as simple as I could. the following code uses two passes, the first pass creates a histogram of character counts. The second pass uses two pointers to walk the string and, using the information in the histogram, decides which characters to keep and which characters to remove.

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char** argv) {
  if (argc < 2) {
    return EXIT_FAILURE;
  }

  int hist[26] = {0};
  char* forwardProbe = argv[1];
  char* rearProbe = forwardProbe;

  while (*forwardProbe) {
    hist[*forwardProbe - 'a']++;
    forwardProbe++;
  }

  forwardProbe = rearProbe;
  while (*forwardProbe) {
    switch (hist[*forwardProbe - 'a']) {
    case 0:
      break;
    case 1:
      *rearProbe = *forwardProbe;
      rearProbe++;
      hist[*forwardProbe - 'a'] = 0;
      break;
    default:
      if (*forwardProbe < *(forwardProbe + 1)
          || (rearProbe == argv[1]? *rearProbe < *forwardProbe
              : *(rearProbe -1) < *forwardProbe) )
        {
          *rearProbe = *forwardProbe;
          rearProbe++;
          hist[*forwardProbe - 'a'] = 0;
      } else {
        hist[*forwardProbe - 'a']--;
      }
      break;
    }
    forwardProbe++;
  }
  *rearProbe = '\0';
  printf("%s\n", argv[1]);
  return EXIT_SUCCESS;
}

- mfalko September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I solved it using HashMap<String, Integer> where hasmap value contains the max index on that character.

Like in this case the HashMap results in {d=4, b=6, c=7, a=2} ..

In second iteration I just compare the index of the current char and hashmap value if index value is equal that hasmap value just put it in the finalList.

package algo;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Lexicographical {

	public static void main(String args[]) {
		String input = "cbacdcbc";
		String[] arr = getArrayFromString(input);
		Lexicographical lx = new Lexicographical();
		lx.parseList(arr);
	}

	public void parseList(String[] list) {
		HashMap<String, Integer> map = new HashMap<String, Integer>();

		int index = 0;
		for (String i : list) {
			if (map.containsKey(i)) {
				if (map.get(i) < index) {
					map.put(i, index);
				}
			}else{
				map.put(i, index);
			}
			index++;
		}
		index = 0;
		List<String> finalList = new ArrayList<String>();
		for (String i : list) {
			if (index >= map.get(i)) {
				finalList.add(i);
			}
			index++;
		}
		print(finalList);
	}

	public void print(List<String> list) {
		for (String k : list) {
			System.out.print(k + " ");
		}

	}

	public static String[] getArrayFromString(String str) {
		String[] arr = null;
		if (str != null && str.length() > 0) {
			arr = new String[str.length()];
			for (int i = 0; i < str.length(); i++) {
				arr[i] = str.substring(i, i + 1);
			}
		}
		return arr;
	}
}

- catsnow9 September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You code just gives the last positions of all the unique characters, that may not be lexicographical ascending order!
Eg: Adding a to your input gives a wrong answer (i.e.) cbacdcbca gives dbca
while the correct answer should be adbc

- Anonymous September 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correct answer for "cbacdcbca" is "acdb".

- tahtisilma September 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) Complexity solution (more specifically, it is O(26 + n + 26 log 26 + n 26 log 26) ) , using O(n) memory assuming ASCII characters:

public static String processStr(String str){
    if(str == null){
        throw new NullPointerException();
    }
    
    Stack<Integer>[] charStack = new Stack<Integer>[26];
    for(int i = 0; i < 26; i++){
        charStack[i] = new Stack<Integer>();
    }
    for(int i = 0; i < str.length; i++){
        charStack['a' - str.charAt(i)].add(i);
    }

    String result = genString(charStack, -1);
    for(int i = 0; i < 26; i++){
        String check = null;
        while((check = genString(charStack, i)) != null && check.compareTo(result) < 0){
            result = check;
            charStack[i].pop();
        }
    }
    return result;
}

private static String genString(Stack<Integer>[] charStack, int peek){
    if(charStack[peek].size() < 2){
        return null;
    }
    ArrayList<CharObj> charObjs = new ArrayList<CharObj>();
    for(int i = 0; i < 26; i++){
        if(i == peek){
            charObjs.add(new CharObj(charStack[i].get(1), (char)('a'+i));
        }
        else{
             if(charObjs.size() > 0){
                 charObjs.add(new CharObj(charStack[i].peek(), (char)('a'+i));
             }
        }
    }
    return genString(charObjs);
}

private static String genString(ArrayList<CharObj> charObjs){
    Collections.sort(charObjs);
    StringBuilder builder = new StringBuilder();
    for(CharObj charObj : charObjs){
        builder.append(charObj.c);
    }
    return builder.toString();
}

private static class CharObj implements Comparable<CharObj>{
    int index;
    char c;

    CharObj(int index, char c){
        this.index = index;
        this.c = c;
    }

    public int compareTo(CharObj obj){
        return this.index = obj.index;
    }
}

- zortlord September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

What do you think about this algorithm? I haven't had a chance to program but, want your views on the algorithm. Thanks
1 - iterate through the strings backwards.
2 - for each character, take the first occurrence
3 - for each subsequent occurrence, only take it if the current character is less than the character at the next lowest index.

so like this:
0 1 2 3 4 5 6 7
c b a c d c b c

1. iterate backwards
c - 7 (first occurrence)
b - 6 (first occurrence)
c - (is 'c' smaller than character at index 6? No. keep 'c' at 7)
d - 4 (first occurrence)
c - (is 'c' smaller than the character at index 4? Yes. change 'c' index to 3)
a - 2 (first occurrence)
b - (is 'b' smaller than the character at index 2? No. keep 'b' at 6)
c - (is 'c' smaller than the character at index 2? No. keep 'c' at 3)

Finally, you get this:
b - 6
d - 4
c - 3
a - 2

write them in a sorted order according to index and you'll get "acdb"

Thoughts??

- krutin September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'd like to point out one thing though. You don't need to sort for Step 3.

Instead, just iterate through the string again and for each character, check if the current index is the same as the index we have stored for that character in our map. If it is, print it, or store it in the return string.

for (int i = 0; i < str.length(); i++)
{
	if (i == map[str[i]])
		retStr = retStr + str[i];
}

- krutin September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Why won't my posts show up??

Anyways, here's my code:

#include <iostream>
    #include <map>
    #include <string>
     
    using namespace std;
     
    string lexicographical(string str);
     
    int main() {
    	// your code goes here
     
    	cout << lexicographical("abcadaba");
     
    	return 0;
    }
     
    string lexicographical(string str)
    {
    	map<char, int> hashmap;
     
    	map<char, int>::iterator it;
     
    	string retStr = "";
    	int smallest_used_index = str.length();
     
     
    	// Iterate through the string backwards and store each character's
    	// index based on these conditions:
    	// 1 - if first occurrence of the character, store the index
    	// 2 - if not first occurrence, is the current character smaller than
    	//	   the character at the smallest index in use thus far?  If so, 
    	//	   replace this character's existing index with the current index
    	//
    	for (int i = str.length() - 1; i >= 0; i--)
    	{
    		if (hashmap.find(str[i]) == hashmap.end())	// Character isn't in our map
    		{
    			hashmap[str[i]] = i;		// Store this character and its index
    			smallest_used_index = i;	// Update the smallest_used_index with this one
    		}
    		else	// Character IS in our map
    		{
    			if (str[i] <= str[smallest_used_index])	// Current haracter is smaller than the character at the smallest index thus far
    			{
    				hashmap[str[i]] = i;		//overwrite this character's existing index with the current index
    				smallest_used_index = i;	//now use THIS as the smallest_used_index
    			}
     
    		}
    	}
     
    	// Once the Map is created, just go through each letter in the string and print
    	// the character as long as that character's index in the string matches what's
    	// stored in the map
    	for (int i = 0; i < str.length() ; i++)
    	{
    		if (hashmap[str[i]] == i)
    			retStr = retStr + str[i];
    	}
     
    	return retStr;
    }

- krutin September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This solution doesn't work for "cacasc".
Backward iteration yields:
Take c at 5th index. (first occurance)
Take s at 4th index. (first occurance)
Take a at 3th index. (first occurance)
Skip c at 2th index. (c is lexicographically not smaller than a at 3th index)
Skip a at 1th index. (a is lexicographically not smaller than a at 3th index)
[You can also take this a. It doesn't change anything]
Skip c at 0th index. (c is lexicographically not smaller than a)

now we have {c: 5, s: 4, a: 3} or {c: 5, s: 4, a: 1} depending on the implementation.
In both cases we end up with "asc", which is obviously wrong answer. It should be "acs" with {a: 1, c: 2, s:4}.

- can September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Never mind, understood, the next lowest index is the lowest index of any char in the input string already used in the solution. Good job!

- DManchala16@students.claremontmckenna.edu September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Never mind, can is right, just tested.

- DManchala16@students.claremontmckenna.edu September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Tried "cacasc" with krutin's C++ code, and it does NOT produce the correct answer. It outputs "asc" instead of "acs".

- can September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can, what about this O(n^2) solution?

string smallestUniqueCharSubsequence(const string& s) {
  
  string solution;
  solution += s[0];
  
  for (int i = 1; i < s.size(); ++i) {
    
    int j;
    for (j = solution.size() - 1; j >= 0; --j) {
      
      if (s[i] == solution[j]) {
        if(static_cast<int>(solution[j + 1]) < static_cast<int>(solution[j])) {
          solution.erase(solution.begin() + j);
          solution += s[i];
        }
        break;
      }
    }
    
    if (j == -1) {
      solution += s[i];
    }
  }
  return solution;
}

- DManchala16@students.claremontmckenna.edu September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this does not work in all the cases - Take a simple example : "bcabc"
The algorithm above will give us "bac" where as the correct solution is "abc"
Am I missing something?

- Katamaran September 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this wont work in all cases. Consider "bcabc" - The algorithm will give us "bac", where as the right solution is "abc".

- Katamaran September 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, I came up with almost the same approach and it works. But my version works fine with test case "bcabc" and returns "abc", because of another way of comparison.
Please find on this page Ctrl+F -> manzhos.max
it would be my post with details

Well, this comment of user @can
"Tried "cacasc" with krutin's C++ code, and it does NOT produce the correct answer. It outputs "asc" instead of "acs"."
killed my approach :(

- manzhos.max September 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if we use similar logic but parse the string from the start instead of starting from the end?

While comparing similar occurrences we check with the next character and choose the option which is lexicographically smaller. For ex.
"bcabcd"
1. First occurrence of b - keep it
2. First occurrence of c - keep it
3. First occurrence of a - keep it
4. Second occurrence of b - compare "bca" with "bcd". Always keep occurrences of letters that are less than the next letter to keep the lexicographical value small. We choose the latter and hence re,one the first b. Now the string is "cabcd".
5. Second occurrence of c - compare "ca" with "cd" . Keep the latter . New string is "abcd".

- Optimus September 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar with catsnow9's idea.

def removeDuplicatedLetters(s):
    # First scan
    dict, ret = {}, []
    for i in xrange(len(s)):
        if s[i] not in ret:
            ret.append(s[i])
            dict[s[i]] = i
        else:
            ret.remove(s[i])
            ret.append(s[i])
            dict[s[i]] = i

    ind = dict.values()
    # Second scan
    for i in xrange(len(s)):
        if s.index(s[i]) in ind:
            continue
        temp = dict[s[i]]
        dict[s[i]] = i
        lst = sorted(dict.keys(),key = lambda d:dict[d])
        if ''.join(lst) < ''.join(ret):
            ret = lst
        else:
            dict[s[i]] = temp
    return ''.join(ret)

if __name__ == "__main__":
    l1 = 'cbacdcbc'
    l2 = 'bcabc'
    print removeDuplicatedLetters(l1)   # acdb
    print removeDuplicatedLetters(l2)   # abc

- akak18183 September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are checking if "in ret" which is an O(N) operation. I think that is not a good thing to do.

- nil September 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does anyone have an O(n) solution? This is an O(n^2) solution:

string smallestUniqueCharSubsequence(const string& s) {
  
  string solution;
  solution += s[0];
  
  for (int i = 1; i < s.size(); ++i) {
    
    int j;
    for (j = solution.size() - 1; j >= 0; --j) {
      
      if (s[i] == solution[j]) {
        if(static_cast<int>(solution[j + 1]) < static_cast<int>(solution[j])) {
          solution.erase(solution.begin() + j);
          solution += s[i];
        }
        break;
      }
    }
    
    if (j == -1) {
      solution += s[i];
    }
  }
  return solution;
}

- DManchala16@students.claremontmckenna.edu September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, take a look at my post

- krutin September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++, O(n)

#include <iostream>
#include <string>

using namespace std;

string removeDupAndSort(string& s) {
	int i, f[123] = {0, };
	string result;

	for (i = 0; i < s.size(); i++) f[ s[i] ] = 1;
	for (i = 'a'; i <= 'z'; i++) if (f[i] == 1) result.push_back(i);

	return result;
}

int main(int argc, char* argv[]) {
	string s = "bcabc";

	cout << removeDupAndSort(s) << "\n";

	return 0;
}

- kyduke September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution doesn't work for cba (or ccbbaa)

- eigelc September 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Sort the characters
2. Remove duplicates

public static String removeDupAndOrder(String string) {
		
		if(string == null || string.isEmpty()) {
			return string;
		}
		
		char[] charArray = string.toCharArray(); 
		Arrays.sort(charArray);
		
		StringBuilder sb = new StringBuilder(String.valueOf(charArray));
		
		char currentChar = '\0';
		
		for(int i = 0; i < sb.length(); i++) {
			if(currentChar != sb.charAt(i)) {
				currentChar = sb.charAt(i);
			} else {
				sb.deleteCharAt(i);
				i--;
			}
		}
		
		return sb.toString();
	}

- june.pravin September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution, O(n)

public static String lowest(String input) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < input.length(); i++) {
                Character c = input.charAt(i);
                int index = sb.indexOf(c.toString());
                if (index == -1) {
                    sb.append(c);
                } else {
                	String first = sb.toString();
                	sb.deleteCharAt(index);
                	sb.append(c);
                	String second = sb.toString();
                	if (first.compareTo(second) < 0) sb = new StringBuilder(first);
                }
            }
            return sb.toString();
        }

- louis September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry for all the duplicate posts.... didn't see them, and not sure how to delete

- louis September 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

bcabc, your solutions returns wrong answer

- hanks October 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution is wrong

- hanks October 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution works by computing the solution using all characters up to 'i' in each loop. So, after the end of the loop, all the characters are considered, and it is the solution to the original input.

There are 2 cases for the next considered character:
1) It hasn't been seen before. In this case, just add it to the end of the solution string.
2) It has been seen before. In this case, compare the current solution with the solution you get by moving that character to the end of the current solution.

Although each loop can potentially consider all characters in the solution (e.g. indexOf), this runs in O(n) time because there are at most 26 characters in the solution string.

public static String lowest(String input) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < input.length(); i++) {
                Character c = input.charAt(i);
                int index = sb.indexOf(c.toString());
                if (index == -1) {
                    sb.append(c);
                } else {
                	String first = sb.toString();
                	sb.deleteCharAt(index);
                	sb.append(c);
                	String second = sb.toString();
                	if (first.compareTo(second) < 0) sb = new StringBuilder(first);
                }
            }
            return sb.toString();
        }

- louis September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

not work for cbacdbced. expect abced, actual output: acbed

- jiangok2006 November 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't understand the question. What does "lexicographical order of the new string is smallest" mean?

- Teh Kok How September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't understand the question. What does "lexicographical order of the new string is smallest" mean?

- Teh Kok How September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is C# version of solution. i have used stack & hashset to build result . it will be defiantly less than O(2*N)

static void Main(string[] args)
        {
            do
            {
                Console.WriteLine("please enter string");
                var str = Console.ReadLine();
                var result = LexicoGraphical(str);
                Console.WriteLine("LexicoGraphical order string is {0}\npress any key to continue or endkey to exit" , result);


            } while (Console.ReadKey().Key != ConsoleKey.End);
          

            Console.ReadLine();

        }

        static string LexicoGraphical(string inputData)
        {
            //hashset will keep track on passed char 
            var passedCharSet = new HashSet<char>();
            // we can make use of stack LIFO behaviour to build result 
            var resultSet = new Stack<char>();
            
            
            for (int index = inputData.Length - 1; index >= 0; index--)
            {
                var currentChar = inputData[index];
                if (!passedCharSet.Contains(currentChar))
                {
                    passedCharSet.Add(currentChar);
                    resultSet.Push(currentChar);
                }
                else if (currentChar < inputData[index+1])
                {
                 // add char to stack & we can skip old position of char by ignoring it in 2nd pass 
                   resultSet.Push(currentChar);
                }
            }


            passedCharSet = new HashSet<char>();
            var resultEnum = resultSet.GetEnumerator();
            StringBuilder builder = new StringBuilder();
            
            while (resultEnum.MoveNext())
            {
                //skip char who's index is changed  in 1st pass 
                if (!passedCharSet.Contains(resultEnum.Current))
                {
                    builder.Append(resultEnum.Current);
                    passedCharSet.Add(resultEnum.Current);
                }
                
            }

        
            return builder.ToString();
        }

- paku September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but if input string is abcacbd this algorithm return acdb but best answer if abcd.

- pavelmehnin September 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A solution in C++11:

static string _form_string(const map<char, int> &use_index)
{
    using content_type = pair<char, int>;
    vector<content_type> content;
    for (auto it = use_index.begin(); it != use_index.end(); ++it)
    {
        content.push_back(*it);
    }

    std::sort(content.begin(), content.end(),
            [](const content_type &first, const content_type &second) -> bool
            {
                assert (std::get<1>(first) != std::get<1>(second));
                return std::get<1>(first) < std::get<1>(second);
            });

    string result;
    for (auto &i : content)
    {
        result += std::get<0>(i);
    }
    return result;
}


string delete_dupes(const string &input)
{
    map<char, int> use_index;   // maps a character in the string to its use index
                                // e.g. if "abc" is formed from "bcabc", then
                                //      'a':2, 'b':3, 'c':4
    string result;

    // first pass: greedily select the last character found (discarding earlier dupes)
    for (int i = 0; i < (int)input.size(); ++i)
    {
        char c = input[i];
        auto found = result.find(c);
        if (found != string::npos)
        {
            // a new duplicate character found; erase our usage of its earlier occurence
            result.erase(found, 1);
        }
        result += c;
        use_index[c] = i;
    }

    // at this point, we have a candidate string that should contain no duplicate
    // characters, and we've also kept track of the last index of each character
    // that we used to form this candidate string
    assert (use_index.size() == result.size());

    // second pass: for each duplicate character, try each of its earlier indices
    //              and greedily persist only if a smaller (lexicographically) string
    //              can be formed
    for (int i = 0; i < (int)input.size(); ++i)
    {
        char c = input[i];
        if (use_index[c] == i)
        {
            // the current candidate string already uses this character at this index
            continue;
        }

        int temp = use_index[c];

        // tentatively try using a character from this index, instead
        use_index[c] = i;
        // and see if the string formed is lexicographically smaller
        string candidate = _form_string(use_index);
        if (candidate < result)
        {
            result = candidate;
        }
        else
        {
            // not smaller, discard that attempt and restore our use index
            use_index[c] = temp;
        }
    }

    return result;
}


int main()
{
    vector<tuple<string, string>> tests{
        tuple<string, string>{ "bcabc", "abc" },
        tuple<string, string>{ "cbacdcbc", "acdb" },
    };

    for (auto &test : tests)
    {
        string &input = std::get<0>(test);
        string &expected = std::get<1>(test);
        
        string output = delete_dupes(input);
        cout << input << " -> " << output << endl;

        assert (output == expected);
    }

    return 0;
}

- Santoso.Wijaya September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the first round, just count the frequency of each char. During the second scan, at each occurrence, print it out if its the last occurrence or if no lower char (lexi speaking) exists anymore in the further location. Here is the java code. Note that cbacdcbc prints out adbc which is lexicographically in the same order as acdb

import java.util.Arrays;
import java.util.HashMap;
import java.util.Set;

public class DeletRepeatedLexi {
	public static int getIndex(Character[] array, char c) {
		for (int i=0; i < array.length;i++)
			if (array[i] == c)
				return i;
		return -1;
	}
	public static HashMap<Character,Integer> getFrequency(String st)
	{
		HashMap<Character,Integer> counter= new HashMap<Character, Integer>();
		for (int i=0;i<st.length();i++)
		{
			char c = st.charAt(i);
			if (counter.get(c) == null)
			{
				counter.put(c, 0);
			}
			counter.put(c, counter.get(c)+1);
			
		}
		return counter;
	}
	private static boolean lowerStillExists(Character[] charArray, HashMap<Character, Integer> counter, char c) {
		int index = getIndex(charArray, c);
		for (int i=0;i<index;i++)
			if (counter.get(charArray[i]) > 0)
				return true;
		return false;
	}
	public static String lexicographical(String st)
	{
		HashMap<Character,Integer> counter = getFrequency(st) ;
		
		//get sorted array of the characters that occured. Note that it can be max 26, so O(1) for sorting.
		Set<Character> s = counter.keySet();
		Character[] charArray = s.toArray(new Character[0]);
		Arrays.sort(charArray);
		
		
		String finalString="";
		for (int i=0;i <st.length();i++)
		{
			char c = st.charAt(i);
			int numbersRemaining = counter.get(c);
			if (!lowerStillExists(charArray, counter, c) || numbersRemaining ==1)
			{
				if (numbersRemaining >0) {
					finalString=finalString+c;
					counter.put(c, -1);
				}
			}
			else
				counter.put(c,numbersRemaining-1);
		}
		return finalString;
		
		
	}
	

	public static void main(String[] args) {
		System.out.println(lexicographical("cbacdcbc"));
		System.out.println(lexicographical("acbac"));
		System.out.println(lexicographical("abcadaba"));
		System.out.println(lexicographical("acbac"));

	}

}

- AbstractInstance September 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1)Sorry for the dupes. Not sure what happened there.
2)if (numbersRemaining >;0) should have been if (numbersRemaining >0)

- AbstractInstance September 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the first round, just count the frequency of each char. During the second scan, at each occurrence, print it out if its the last occurrence or if no lower char (lexi speaking) exists anymore in the further location. Here is the java code. Note that cbacdcbc prints out adbc which is lexicographically in the same order as acdb

import java.util.Arrays;
import java.util.HashMap;
import java.util.Set;

public class DeletRepeatedLexi {
	public static int getIndex(Character[] array, char c) {
		for (int i=0; i < array.length;i++)
			if (array[i] == c)
				return i;
		return -1;
	}
	public static HashMap<Character,Integer> getFrequency(String st)
	{
		HashMap<Character,Integer> counter= new HashMap<Character, Integer>();
		for (int i=0;i<st.length();i++)
		{
			char c = st.charAt(i);
			if (counter.get(c) == null)
			{
				counter.put(c, 0);
			}
			counter.put(c, counter.get(c)+1);
			
		}
		return counter;
	}
	private static boolean lowerStillExists(Character[] charArray, HashMap<Character, Integer> counter, char c) {
		int index = getIndex(charArray, c);
		for (int i=0;i<index;i++)
			if (counter.get(charArray[i]) > 0)
				return true;
		return false;
	}
	public static String lexicographical(String st)
	{
		HashMap<Character,Integer> counter = getFrequency(st) ;
		
		//get sorted array of the characters that occured. Note that it can be max 26, so O(1) for sorting.
		Set<Character> s = counter.keySet();
		Character[] charArray = s.toArray(new Character[0]);
		Arrays.sort(charArray);
		
		
		String finalString="";
		for (int i=0;i <st.length();i++)
		{
			char c = st.charAt(i);
			int numbersRemaining = counter.get(c);
			if (!lowerStillExists(charArray, counter, c) || numbersRemaining ==1)
			{
				if (numbersRemaining >0) {
					finalString=finalString+c;
					counter.put(c, -1);
				}
			}
			else
				counter.put(c,numbersRemaining-1);
		}
		return finalString;
		
		
	}
	

	public static void main(String[] args) {
		System.out.println(lexicographical("cbacdcbc"));
		System.out.println(lexicographical("acbac"));
		System.out.println(lexicographical("abcadaba"));
		System.out.println(lexicographical("acbac"));

	}

}

- AbstractInstance September 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the first round, just count the frequency of each char. During the second scan, at each occurrence, print it out if its the last occurrence or if no lower char (lexi speaking) exists anymore in the further location. Here is the java code. Note that cbacdcbc prints out adbc which is lexicographically in the same order as acdb

import java.util.Arrays;
import java.util.HashMap;
import java.util.Set;

public class DeletRepeatedLexi {
	public static int getIndex(Character[] array, char c) {
		for (int i=0; i < array.length;i++)
			if (array[i] == c)
				return i;
		return -1;
	}
	public static HashMap<Character,Integer> getFrequency(String st)
	{
		HashMap<Character,Integer> counter= new HashMap<Character, Integer>();
		for (int i=0;i<st.length();i++)
		{
			char c = st.charAt(i);
			if (counter.get(c) == null)
			{
				counter.put(c, 0);
			}
			counter.put(c, counter.get(c)+1);
			
		}
		return counter;
	}
	private static boolean lowerStillExists(Character[] charArray, HashMap<Character, Integer> counter, char c) {
		int index = getIndex(charArray, c);
		for (int i=0;i<index;i++)
			if (counter.get(charArray[i]) > 0)
				return true;
		return false;
	}
	public static String lexicographical(String st)
	{
		HashMap<Character,Integer> counter = getFrequency(st) ;
		
		//get sorted array of the characters that occured. Note that it can be max 26, so O(1) for sorting.
		Set<Character> s = counter.keySet();
		Character[] charArray = s.toArray(new Character[0]);
		Arrays.sort(charArray);
		
		
		String finalString="";
		for (int i=0;i <st.length();i++)
		{
			char c = st.charAt(i);
			int numbersRemaining = counter.get(c);
			if (!lowerStillExists(charArray, counter, c) || numbersRemaining ==1)
			{
				if (numbersRemaining >0) {
					finalString=finalString+c;
					counter.put(c, -1);
				}
			}
			else
				counter.put(c,numbersRemaining-1);
		}
		return finalString;
		
		
	}
	

	public static void main(String[] args) {
		System.out.println(lexicographical("cbacdcbc"));
		System.out.println(lexicographical("acbac"));
		System.out.println(lexicographical("abcadaba"));
		System.out.println(lexicographical("acbac"));

	}

}

- AbstractInstance September 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

does not work for cdabc. expect: cdab, actual: dabc

- jiangok2006 November 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Test

- AbstractInstance September 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Test

System.out.println("hello");

- AbstractInstance September 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not really sure if Python's defaultdict constitutes a fair answer. But this is my code:

from collections import defaultdict

char_list = ['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']
char_to_idx = {char_list[idx]: idx for idx in xrange(len(char_list))}
idx_to_char = {idx: char_list[idx] for idx in xrange(len(char_list))}


def parse_to_idx(raw_string):
	result = []
	for each_char in raw_string:
		result.append(char_to_idx[each_char])
	return result

def parse_to_str(list_idx):
	result = ''
	for idx in list_idx:
		result += idx_to_char[idx]
	return result

def compare_num_to_list(base_list, lists_of_nums):
	""" Return true if base list contains number smaller than all the
	largest numbers in lists_of_nums """

	for each_list in lists_of_nums:
		if min(base_list) > max(each_list):
			return False
	return True

def update_occurrence(num, occurrence):
	""" Delete any number smaller than num in the occurrence """

	result = defaultdict(list)
	for key, value in occurrence.items():
		for each_value in value:
			if each_value > num:
				result[key].append(each_value)
	return result


def choose_leftmost(occurrence):
	""" Choose the leftmost character """

	all_keys = occurrence.keys()
	all_values = occurrence.values()
	for idx_root, key in enumerate(all_keys):
		if idx_root == len(all_keys): return (key, max(occurrence[key]))
		base_list = occurrence[key]
		lists_of_nums = []
		for subsequent_key in all_keys[idx_root+1:]:
			lists_of_nums.append(occurrence[subsequent_key])
		if compare_num_to_list(base_list, lists_of_nums) == False:
			continue
		else:
			return (key, min(base_list))


def run(raw_string):

	## initialize all working variables
	raw_string = raw_string.lower()
	idx_string = parse_to_idx(raw_string)
	working_string = []

	## dictionary to keep track of the index of the characters (numbers)
	occurrence = defaultdict(list)
	for idx, each_char in enumerate(idx_string):
		occurrence[each_char].append(idx)
	all_keys = occurrence.keys()
	
	while len(occurrence.keys()) != 0:
		key, num = choose_leftmost(occurrence)
		working_string.append(key)
		occurrence.pop(key)
		occurrence = update_occurrence(num, occurrence)

	working_string = parse_to_str(working_string)

	return working_string


print run('lksakwoabpocdais')

- giangnguyen1208 September 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Main {
    public static void main(String args[]) {
        System.out.println(uniqueMinLex("cbacdcbc"));
    }


    private static String uniqueMinLex(String s) {
        
        // FIRST PASS: find the last index of each character
        Map<Character, Integer> lastIndex = new HashMap<Character, Integer>();
        Set<Character> included = new HashSet<Character>();
        for(int i=0;i<s.length();i++) {
            lastIndex.put(s.charAt(i), i);
        }

        // SECOND PASS: BUILD THE SOLUTION IN A STACK
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<s.length();i++) {
            char ch = s.charAt(i);
            // POP FROM STACK CHARS LARGER THAN CH IF THERE WILL BE MORE OF THEM   
            while(
                    sb.length() > 0 && lastChar(sb) > ch // CH IS SMALLER THAN TOP OF STACK
                            && 
                            lastIndex.get(lastChar(sb)) > i) { // THERE WILL BE MORE OF THE CHAR AT TOP OF STACK
                included.remove(lastChar(sb));
                sb.delete(sb.length()-1, sb.length());
            }
            
            if(! included.contains(ch)) {
                // CH IS NOT IN SOLUTION YET - ADD IT
                sb.append(ch);
                included.add(ch);
            }
        }
        return sb.toString();
    }

    private static char lastChar(StringBuilder sb) {
        return sb.charAt(sb.length()-1);
    }
}

- Irit September 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) complexity (I think. It's a hill climber so that's hard to really assess) with O(n) memory.

public static String processStrHillClimber(String str) {
        if (str == null) {
            throw new NullPointerException();
        }
        if (str.length() == 0) {
            return "";
        }

        ArrayList<Integer>[] charSets = buildCharSets(str);
        int[] selected = new int[26];

        boolean improved = false;
        String result = genString(charSets, selected);
        do {
            improved = false;
            for (int i = 0; i < 26; i++) {
                if (charSets[i].size() > 1) {
                    int orig = selected[i];
                    for (int j = charSets[i].size() - 1; j > -1; j--) {
                        selected[i] = j;
                        String check = genString(charSets, selected);
                        if (check.compareTo(result) < 0) {
                            result = check;
                            improved = true;
                            orig = j;
                        }
                    }
                    selected[i] = orig;
                }
            }

        }
        while (improved);
        return result;
    }

    private static String genString(ArrayList<Integer>[] charSets, int[] selected) {
        ArrayList<CharObj> charObjs = new ArrayList<CharObj>();
        for (int i = 0; i < 26; i++) {
            if (charSets[i].size() > 0) {
                charObjs.add(new CharObj(charSets[i].get(selected[i]), (char) ('a' + i)));
            }
        }

        Collections.sort(charObjs);

        StringBuilder builder = new StringBuilder();
        for (CharObj charObj : charObjs) {
            builder.append(charObj.c);
        }
        return builder.toString();
    }

    private static ArrayList<Integer>[] buildCharSets(String str) {
        ArrayList<Integer>[] charSets = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            charSets[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < str.length(); i++) {
            charSets[str.charAt(i) - 'a'].add(i);
        }
        return charSets;
    }

    private static class CharObj implements Comparable<CharObj> {

        int index;
        char c;

        CharObj(int index, char c) {
            this.index = index;
            this.c = c;
        }

        public int compareTo(CharObj obj) {
            return this.index - obj.index;
        }
    }

- zortlord September 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/python

import sys
from string import ascii_lowercase

L=list(ascii_lowercase)
istr="cbacdcbc"
istr="bcabc"
lstr=list(istr)
nstr=[]
for i in lstr:
    lex=lstr[1:]
    if i in lex and lstr.index(i) != len(lstr)-1:
        lstr=lstr[1:]
    else:
        nstr.append(i)
        lstr=lstr[1:]

print ''.join(nstr)

- Anonymous September 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/python

import sys
from string import ascii_lowercase

L=list(ascii_lowercase)
istr="cbacdcbc"
istr="bcabc"
lstr=list(istr)
nstr=[]
for i in lstr:
    lex=lstr[1:]
    if i in lex and lstr.index(i) != len(lstr)-1:
        lstr=lstr[1:]
    else:
        nstr.append(i)
        lstr=lstr[1:]

print ''.join(nstr)

- Anonym September 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution given below takes linear time and O(1) memory.

def removeDuplicates(_str):
	val = 0 # Integer: We'll use the 26 least significant bits to keep track of which characters have been seen

	pos = [-1 for i in range(26)] #Which occurence (index) of a character are we keeping	
	max_val = [0 for i in range(26)]

	for i in range(len(_str)):
		curr_char = _str[i]
                
		val = val | (1<<(ord(_str[i])-ord('a')))
		temp_val = 0
		for j in range(ord(_str[i])-ord('a')):
			temp_val = temp_val | 1<<j	
		temp_val = temp_val & val
		if temp_val>max_val[ord(_str[i])-ord('a')] or pos[ord(_str[i])-ord('a')]==-1:
			pos[ord(_str[i])-ord('a')] = i
			max_val[ord(_str[i]) - ord('a')] = temp_val
        

	v = [(chr(i+97), pos[i]) for i in range(26) if pos[i]!=-1]
	v.sort(key = lambda x:x[1])
	return ''.join([k[0] for k in v])

- ayush.jain91 September 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm:

1) Traverses the string once to get the frequency
2) Now going left to right, get the character whose frequency is 1
This character needs to be included
Check for alphabets to the right of this character.
If value less than this character, take the char since it will produce a lower total value.
Mark this duplicate char as taken so we do not consider repeated instances.
Recursively find a character between this and our first reference in a way we found the second character.
When no characters exist, go to next char with frequency 1. Repeat the process
If all characters with frequency 1 are exhausted, go to the right most character and repeat the until all characters get marked.

It is an O(n^2) algorithm

- CSbuddy September 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If there is an efficient algorithm for this problem I doubt it can be devised during the interview. Dynamic programming doesn't really work here because the problem doesn't separate into independent subproblems (the singleton letters must be taken so you can vary only what is between). All people claiming linear algorithms here just didn't give a good thought to testing them. So, I'll stick to the correctly working algorithm that can be realistically coded in 1/2 hour. It is exponential, but there is significant optimization through pruning.

string getSmallest(const string &s, unordered_map<char, queue<int>> &M, int start)
{

	int n = start;
	while ((n < s.size()) && (M.find(s[n]) == M.end())) // Skip the ones that already taken
		n++;

	if (n == s.size())
		return "";

	string incl;
	string excl;
	char c = s[n];
	
	unordered_map<char,queue<int>> Mc(M);
	queue<int> q(Mc[c]);

	Mc.erase(c);
	incl.push_back(c);
	incl += getSmallest(s, Mc, n + 1);

	if (q.size() > 1)
	{
		q.pop();
		Mc[c] = q;
		excl = getSmallest(s, Mc, n + 1);
	}

	if (excl.empty() || incl.compare(excl) < 0)
	{
		return incl;
	}

	return excl;

}

string removeDuplicatesToGetLexMinimum(const string &s)
{
	string res;
	unordered_map<char, queue<int>> M;

	for (int i = 0; i < s.size(); i++)
	{
		char c = s[i];
		M[c].push(i);
	}

	res = getSmallest(s, M, 0);
	return res;
}


void testStringTransformation()
{
	string s = "ecbafcdcbc";
	string r = removeDuplicatesToGetLexMinimum(s);

	cout << "Transforming a string:\n";
	cout << s << " " << r << endl;

	s = "cacasc";
	r = removeDuplicatesToGetLexMinimum(s);
	cout << s << " " << r << endl;

	s = "abcadaba";
	r = removeDuplicatesToGetLexMinimum(s);
	cout << s << " " << r << endl;
}

- AP September 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a solution in C++. Time complexity O(N2)

/* 
Given a string which only contains lowercase. You need delete the repeated letters only leave one, and try to make the lexicographical order of new string is smallest. 
i.e: 
bcabc 
You need delete 1 'b' and 1 'c', so you delete the first 'b' and first 'c', the new string will be abc which is smallest. 

ps: If you try to use greedy algorithm to solve this problem, you must sure that you could pass this case: 
cbacdcbc. answer is acdb not adcb 

I can't solve this problem well and the interviewer said that you can scan the string twice. First scan is do some preprocess, and the second is to get the answer, but I really can't come up this idea.
*/

#include<iostream>
using namespace std;
#include<ctype.h>
#include<string.h>

void createDictionary(char *str,int dictionary[26])
{
	int i=0;
	while(str[i]!='\0')
	{
		dictionary[str[i]-'a']++;
		i++;
	}
}


char* removeDuplicates(char *str,int dictionary[26])
{
	char *result=new char[strlen(str)];
	for(int k=0;str[k]!='\0';k++)
	{
		for(int i='a';i<='z';i++)
		{
			int tempDict[26]={0};
			int j=k;
			while(str[j]!=i && str[j]!='\0')
			{
				if(isalpha(str[j]))
				{
					int index=str[j]-'a';
					tempDict[index]++;
					if(dictionary[index]-tempDict[index]==0)
					{
						break;
					}
				}
				j++;				
			}
			if(str[j]==i)
			{
				if(str[j+1]=='\0' && dictionary[str[j]-'a']>1)
				{
					dictionary[str[j]-'a']--;
					str[j]=' ';
				}
				for(;k<j;k++)
				{
					dictionary[str[k]-'a']--;
					str[k]=' ';
				}
				break;
			}
		}
	}
	int j=0;
	for(int i=0;i<strlen(str);i++)
	{
		if(isalpha(str[i]))
		{
			result[j]=str[i];
			j++;
		}
	}
	result[j]='\0';
	return result;
}

int main()
{
	char str[]="cbacdcbc";
	int dictionary[26]={0};
	createDictionary(str,dictionary);
	
	char *result=removeDuplicates(str,dictionary);
	cout<<result;
	return 0;
}

- technoapurva September 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

removedup(char* input)
{
	int a[256];

	memset(a, 0, 256);

	char*tmp = input;
	int size = 0;

	while(*tmp != ‘\0’){
		a[ (int) (*tmp) ]++;
		size++;
		++tmp;
	}

	output = new char[size];
	int count

	while(*input != ‘\0’){
		if ( a[ (int)(*input) ] > 1)
			a[ (int)(*input) ]  = 1;
		else if (a[ (int)(*input) ] == 1){
			a[ (int)(*input) ] = 0;
			output[count++] = *input;
		}
		++input;
	}

}

- hiuhchan September 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//just practiced this on google doc for prep
public string uniqueWord(string word){
//get the number of the unique letters in the word
int uniqueCounter = 0;
String str = “”;
ArrayList<String> wordCollection = new ArrayList<String>();
HashTable<String,Integer> blockCounter = new HashTable<String,Integer>();
HashTable<String,Integer> uniCounter = new HashTable<String,Integer>();
string [] letters = {a,b,c,d,e,f,g,h,i,g,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z);
for(int i = 0 ; i < 26; i++){
blockCounter.put(letters[i],0);
uniCounter.put(letters[i],0); //to be to determine for word start
}
foreach(char w : word ){ cbabc
//check to see if the value is 0. if not it is a duplicate
if(blockCounter.get(w) == 0){
uniqueCounter++; //its the first encounter so add to counter
blockCounter.remove(w);
blockCounter.put(w,1);
}
}
blockCounter = intialize(blockCounter);
//loops through length of the word minus the unique letters
//this will get all the possible words
for(int i=0;i<(word.length - UniqueCounter; i++){ i -> 2 ,a cbabc
//checks to see if the letter has been used to start a word
if(uniCounter.get(word[i]) == 0){
uniCounter.remove(word[j]);
uniCounter.put(word[j],1); //word has already started with this letter
blockCounter.remove(word[j]);
blockCounter.put(word[j],1);
str += word[i]; c
for(int j=(i+1);j<word.length;j++){
//if its the first encounter of the letter
if(blockCounter.get(word[j]) == 0){
str += word[j]; abc
blockCounter.remove(word[j]);
blockCounter.put(word[j],1);
}
}
wordCollection.add(str); cba, bac, abc
str = ””;
blockCounter =intialize( blockCounter);
}
}
//lets sort it based on lexicographical entry
String strToReturn = wordCollection.get(0);
foreach(String s : wordCollection){
if(s.CompareTo(strToReturn) < 0)
strToReturn = s;
}
return strToReturn;
}
public HashTable<String, Integer> initialize(HashTable<String,Integer> wordList){
for(int i = 0 ; i < 26; i++)
blockCounter.remove(letters[i])
for(int i = 0 ; i < 26; i++)
blockCounter.put(letters[i],0) //initialize hashtable again
}

- r3t September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) preprocessing (time and memory)
O(n) building a solution (time and memory)
So idea is in usage of dynamic programming.
Let's consider an example.
"cbacdcbc"
my first approach was in building new string character by character i.e.
1) c
2) cb
3) cba
4) cbac (aha! duplicate. now let's choose the letter to remove)
4.1) cba > bac, so we choose bac
4.2) for easiness of comparison I used a condition "if earliar (leftmost) duplicate next character
is less than current character then remove earlier occurrence else remove the last character".
In example firstC.next = 'b', 'b' < 'c', remove earlier 'c'
5) bac -> bacd
6) bacd -> bacdc -> bacd
7) bacd -> bacdb -> acdb
8) acdb -> acdbc -> acdb
9) acdb is an answer

Well, it doesn't work with "bcabc", because it would return "bac",
but good news! A simple alrorithm improvement solves this problem, just go from end to the begininng!
It is the only right way to do it, because lexigraphically a string becomes heavier in this order (from right to left), if we consider formula like
"bac" = 2*10^2 + 1*10 + 3

So okay, let's test it with vice-versa approach

test case "bcabc", excpected result "abc"
1) c
2) bc
3) abc
4) cabc -> abc
5) babc -> abc

So approach is doing fine!
Now there are 2 problems:
1) Comparison of examples.
It might be O(n) very for every comparison, but with approach described in the above list in paragraph 4.2 it is O(1)
2) Looking for and removing duplicaes.
Which is even O(n^2) in worst case. So here we should use preprocessing. What kind?
HashMap<Character, LinkedList<Integer>> - linkedlist of character occurences in the array from right to left.
So we could check every insertion of character to out resulting string in O(1) with preprocessed usage of memory in O(n)

I will write a code soon.

- manzhos.max September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Second test case should be:
1) ____c
2) ___bc
3) __abc
4) _cabc -> abc
5) _babc -> abc

- manzhos.max September 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

OMG, I finally found the solution for all test cases in this page:
combine my approach #1 with left to right pass
with #2 with right to left pass
than compare results.

But I am still not sure in the result, because may exist a test case which breaks down things.

- manzhos.max September 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Perhaps not optimal. This is an O(k*n) solution, where k is the size of the alphabet. It maintains an array, 'keep', of length n that reflects whether an element should be kept (can be easily replaced by a bitmap).
1. Perform a scan to decide which elements of the alphabet to include.
2. For each included element, starting from the last perform a scan over the input string.
3. During the per-element scan:
a. Keep track of the last position you found the element 'last_seen'
b. Also keep track of whether any lower elements have been found since the last
position: 'seen_lower'
c. If you hit a higher element, check if it is in 'keep' at that position; if it is not kept, ignore it.
d. Otherwise, if it is a kept higher element, check if lower elements have been detected since 'last_seen'. If none were detected abort the scan for this element. This effectively marks the element as kept at the 'last_seen' position.
e. Otherwise, if lower elements were detected, continue the scan.
f. If the scan ends without running into higher elements with no intervening lower elements. The element in question is marked in 'keep' at the 'last_seen' position.
4. Finally scan the keep array and overwrite the input string with the result.

#define ALPHABET_SIZE 26
#define ALPHABET_BASE 'a'

void
eliminate_rep_lex(char *s) 
{
    int len = strlen(s);
    int freq[26];
    int keep[len];
    int last_seen;
    int seen_lower;
    int i;
    int j;
    int k;

    for (j = 0; j < ALPHABET_SIZE; ++j) {
        freq[j] = 0;
    }   

    for (i = 0; i < len; ++i) {
        j = s[i] - ALPHABET_BASE;
        keep[i] = 0;
        ++freq[j];
    }   

    /*  
     * For each element, starting from the last element 
     * of the alphabet perform a full scan to decide which 
     * occurence of the element to keep.
     */
    for (j = ALPHABET_SIZE - 1; j >= 0; --j) {
        if (freq[j] == 0) {
            continue;
        }

        last_seen = len;
        seen_lower = 0;
        for (i = 0; i < len; ++i) {
            int cur = s[i] - ALPHABET_BASE;

            if (last_seen < i) {
                if (cur < j) {
                    seen_lower = 1;
                }

                /* 
                 * <equal_*> is the alphabet element being checked.
                 * <lower>, <higher> elements that have are ordered lower 
                 *                   or higher in the alphabet respectively 
                 * <other> Either higher or lower elements but not equal
                 *
                 * 1. <equal_1> <lower> <higher> <other>            => keep <equal_1>
                 * 2. <equal_1> <higher> <other> <equal_2>          => keep <equal_1> 
                 * 3. <equal_1> <lower> <higher> <other> <equal_2>  => keep <equal_2> 
                 */
                if ((cur > j) && keep[i] && !seen_lower) {
                    break;
                }
            }
            if (cur == j) {
                last_seen = i;
                seen_lower = 0;
            }
        }

        keep[last_seen] = 1;
    }

    k = 0;
    for (i = 0; i < len; ++i) {
        if (keep[i]) {
            s[k++] = s[i];
        }
    }
    s[k] = '\0';
}

- Lewis September 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It's just greedy algorithm, and it works:

public static String getCompressedString(String source){

        int[] usedChars = new int[256];
        for(int i='a'; i<='z'; i++){
            usedChars[i]=0;
        }

        for(int i=0; i<source.length(); i++){
            usedChars[source.charAt(i)]++;
        }

        for(int i='z'; i>='a'; i--){
            if(usedChars[i]>0){
                String[] strings = getAllVariants(source, (char)i, usedChars[i]);
                source = getMinString(strings);
            }
        }
        return source;
    }

    private static String getMinString(String[] strings){
        String result = strings[0];
        for(int i=1; i<strings.length; i++){
            if(strings[i].compareTo(result) < 0)
                result = strings[i];
        }
        return result;
    }

    private static String[] getAllVariants(String source, char c, int charsCount){
        String[] result = new String[charsCount];
        for(int i=0; i<charsCount; i++){
            result[i]="";
        }

        int index=0;
        for(int i=0; i<source.length(); i++){
            for(int j=0; j<charsCount; j++){
                if(source.charAt(i)!=c){
                    result[j]+=source.charAt(i);
                }else{
                    if(j==index)
                        result[j]+=c;
                }
            }
            if(source.charAt(i)==c)
                index++;
        }
        return result;
    }

- Maxim October 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take an array of 26(assume only small letters present in string). Now this array will store the index of the character in given string. Initially, initialize it with -1. Now traverse string from right to left and change the index value in array based on next promising character.

Consider given string "cbacdcbc". Maintain one variable say 'next_ch' and array 'foo[26]'. Initially,all elements of array is -1. start from right most character and initialize next_ch as 'c'. Now foo[c]==-1, so change it foo[c]=7.
Now the logic is check entry in foo array corresponding to current character. If it is -1 then directly update current index in array and change the value of next_ch as current character. But if value is not -1, then that character is already came in string so check with next_ch. If current character < next_ch. then update the value of foo[current character] to current index. Otherwise leave unchanged. Below is pseudo code for clarification:

string st="cbacdcbc";
int foo[26]={-1};	char next_ch;
int len=st.length();

for(i=len-1;i>=0;i--)
{
	if(foo[st[i]-'a']==-1)
	{
		foo[st[i]-'a']=i;
		next_ch=st[i];
	}
	else
	{
		if(st[i]<next_ch)
		{
			foo[st[i]-'a']=i;
			next_ch=st[i];
		}
	}
}

So according to above logic, final array has only four entry without -1 because only 4 unique character in string.
foo[a]=2; foo[b]=6; foo[c]=3; foo[d]=4;
So generate answer from given string based on above array
cbacdcbc --> **acd*b* --> acdb

time complexity: O(n), n-length of given string
space complexity: O(26)=O(1)

- Yug October 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It doesnt work on this testcase :
acbacb

your ourput: acb
answer : abc

- MehrdadAP October 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Go over the string and store indexes of each char in an int[26] array.
1.1 if the index value in int[26] is -1 then just insert it.
1.2 if the index value is not -1 (i.e. we have seen this char before), check if current index stored in int[26] is greater than the previous seen alphabet index. if current index is smaller then update it.

public static void parse(String s){
		int[] chars = new int[26];
		for(int k=0; k<chars.length; k++)
			chars[k] = -1;
		char[] arr =  s.toCharArray();
		for(int i=0; i< arr.length; i++){
			int charIndex = arr[i]-'a' ;
			if(chars[charIndex] == -1){
				chars[charIndex] = i;				
			}else{
				for(int m=charIndex-1; m >=0; m--){
					if(chars[m] != -1 ){
						if(chars[m] < chars[charIndex]){
							break;
						}else{
							chars[charIndex]=i;
						}
						break;
					}
				}
			
			}
		}
		
		for(int g=0; g < chars.length; g++)
			if(chars[g] != -1)
				System.out.print(" " + chars[g]);
	}

- Dexter November 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

N2 soln with O(N) mem.

import java.util.Stack;
import java.util.Map;
import java.util.HashMap;
import java.util.Vector;

public class printuniquechars {

	public static Map<Character, Vector<Integer>> invertedIndexes = new HashMap<Character, Vector<Integer>>();
	
	/**
	 * insert into stack.
	 * @param s
	 * @param ind
	 */
	public static void insertStack(Stack<Integer> s, int ind) {
		if(s.empty()) {
			s.push(ind);
			return ;
		}
		
		if(s.peek() < ind) {
			Integer poped = s.pop();
			insertStack(s, ind);
			s.push(poped);
		} else {
			s.push(ind);
		}
	}
	
	
	/**
	 * 
	 */
	public static int getNextClosest(char c, int ind) throws Exception {
		Vector<Integer> is = invertedIndexes.remove(c);
		if(is == null) throw new Exception();
		
		for(Integer i : is) {
			if( ind == -1 || i > ind) {
				return i;
			}
		}
		
		return is.get(is.size()-1);
	}
	
	/**
	 * 
	 * @param in
	 * @throws Exception 
	 */
	public static void printUniqCharsinLexic(char[] in) throws Exception {
		if(in == null || in.length == 0) return;
		
		char[] indexes = new char[255];
		
		for(int i =0; i < in.length ; i++) {
			indexes[in[i]] = in[i];
			
			Vector<Integer> is = invertedIndexes.get(in[i]);
			
			if(is == null) {
				is = new Vector<Integer>();
				is.add(i+1);
				invertedIndexes.put(in[i], is);
			} else {
				is.add(i+1);
			}
			
		}
		
		Stack<Integer> sindex = new Stack<Integer>();
		int start = -1;
		for(int i=0; i < indexes.length;i++) {
			
			if(indexes[i] != 0) {
				start = getNextClosest(indexes[i], start);
				System.out.println(" " + start + " " + indexes[i]);
				insertStack(sindex, start);
			}
		}
		
		System.out.println();
		while(!sindex.isEmpty()) {
			System.out.print(in[sindex.pop()-1]);
		}
		System.out.println();
	}
	
	
	public static void main(String[] args) throws Exception {
		String in = "cbacdcbc";
		printUniqCharsinLexic(in.toCharArray());
	}

}

- Guru December 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class AnalyzeStrings
{
public static void main(String args[])
{
String to_analyze="bcabc";
int[] count=new int[26];
int[] pos=new int[26];
char[] characters=to_analyze.toCharArray();
for(int i=0;i<characters.length;i++)
{
System.out.println(characters[i]-97);
if(count[characters[i]-97]<2)
{
pos[characters[i]-97]=i+1;
count[characters[i]-97]+=1;
}
}
char[] finalChar=new char[26];

for(int i=0;i<26;i++)
{
if(pos[i]!=0)
{
finalChar[pos[i]-1]=(char) Character.toLowerCase(i+97);
}
}
StringBuffer s=new StringBuffer();
for(int i=0;i<26;i++)
{
if(finalChar[i]!='\0')
{
s.append(finalChar[i]);
}
}
System.out.println(s.toString());
}
}

- erswatigarg18 January 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class RemoveCharOptimizer {

	public static void main(String[] args) {
		System.out.println(getMinLexReplacedString("cbacdcbc"));
		System.out.println(getMinLexReplacedString("xyzadatyxzttttacacacbcbbb"));
		
	}
	
	public static String getMinLexReplacedString(String s) {
		if (s == null || s.equals("")) {
			return null;
		}
		Map<Character, Integer> mapChars = new HashMap<>();
		int cnt = 0;
		char c;
		char[] chars = s.toCharArray();
		int n = s.length();
		boolean toRemove[] = new boolean[n];
		boolean searchMore = false;
		
		for (int i = 0; i < n; i++) {
			if (!mapChars.containsKey(chars[i])) {
				mapChars.put(chars[i], 1);
			} else {
				cnt = mapChars.get(chars[i]);
				mapChars.put(chars[i], cnt + 1);
			}			
		}
		
		for (int i = 0; i < n; i++) {
			c = chars[i];
			cnt = mapChars.get(c);
			if (cnt > 1) {			
				if (i + cnt >= (n - 1)) {
					cnt--;
					mapChars.put(c, cnt);
					toRemove[i] = true;
				} else {
					searchMore = true;
					if ((i + 1) < n && Character.compare(c, chars[i + 1]) < 0 && mapChars.get(chars[i + 1]) == 1) {
						searchMore = false;
					}					
					for (int j = i + 1; j < n && searchMore; j++) {
						if (Character.compare(c, chars[j]) > 0) {							
							cnt--;
							mapChars.put(c, cnt);
							toRemove[i] = true;							
							searchMore = false;
						}
					}
				}			
			}
		}

		StringBuilder sb = new StringBuilder();
		mapChars = new HashMap<>();		
		for (int i = 0; i < toRemove.length; i++) {
			if (!toRemove[i] && !mapChars.containsKey(chars[i])) {
				sb.append(chars[i]);
				mapChars.put(chars[i], 1);
			}
		}
		
		return sb.toString();
	}
}

- guilhebl May 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
	Author	: Tom Choi
	Date	: 09/07/2016


	1. Build the lexicographically smallest string as you read one by one
		a. Initialize HashMap of (character, index) pairs
		b. Initialize empty string for result
		c. Read a character
			(i)	If map doesn't have a character, add it to the result
			(ii)If map has a character, then compare it to the string either
				- with the prev result
				- with the redundant char removed and added the char
		
		OPT[k] = min(without char k, with char k)

	Example
		Iteration			Lexocigraphically Min
		c			-> 		c
		cb			->		c b
		cba			->		c b a
		cbac	 	->		min(cba, bac) = bac
		cbacd		->		bacd
		cbacdc		->		min(bacd, badc) = bacd
		cbacdcb		->		min(bacd, acdb)	= acdb
		cbacdcbc	->		min(acdb, adbc)	= acdb
*/

import java.util.*;

public class MinLexicoOrder{
	
	// stores the characters in the string
	private HashSet<Character> set;
	private String input;
	
	public MinLexicoOrder(String input){
		this.set = new HashSet<Character>();
		this.input = input;
	}
	
	public String minString(){
		StringBuilder result = new StringBuilder();
		char[] arr = input.toCharArray();
		for(int i = 0; i < arr.length; i++){
			char c = arr[i];
			
			// first occurrence of the character
			if(!set.contains(c)){
				result.append(c);
				set.add(c);
			}
			// more than one same character
			else{
				// the index of the first conflicting character in the result
				int prev = result.indexOf(String.valueOf(c));
				
				// remove the previous char and append the new one
				StringBuilder temp = new StringBuilder(result);
				temp.deleteCharAt(prev);
				temp.append(c);
				
				// compare the previous minimum string and the current string
				String minimum = min(result.toString(), temp.toString());
				
				// carry the lexicographically smallest string found so far
				result = new StringBuilder(minimum);
			}
		}
		return result.toString();
	}
	
	// compare two strings and return the smaller one
	private String min(String i, String j){
		return (i.compareTo(j) < 0) ? i : j;
	}
	
	public static void main(String[] args){
		String str = "cbacdcbc";
		MinLexicoOrder min = new MinLexicoOrder(str);
		System.out.println(min.minString());
	}
}

Obviously the run time is O(n) because it finds the lexicographically smallest string by reading the characters from the beginning to the end once.

- TChoi September 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution

public static void main(String args[])
    {
        String str="aa";
        deleteRepeated(str);
    }

    private static void deleteRepeated(String str)
    {
        StringBuilder sb=new StringBuilder();
        HashSet<Character> existSet = new HashSet<Character>();
        HashSet<Character> toBeDeletedSet = new HashSet<Character>();
        for(int i=0;i<str.length();i++)
        {
            char c = str.charAt(i);
            if(existSet.contains(c))
            {
                toBeDeletedSet.add(c);
            }
            else
            {
                existSet.add(c);
            }
        }
        for(int i=0;i<str.length();i++)
        {
            char c = str.charAt(i);
            if(toBeDeletedSet.contains(c))
            {
                toBeDeletedSet.remove(c);
            }
            else if(existSet.contains(c))
            {
                sb.append(c);
                existSet.remove(c);
            }
        }
        System.out.println(sb.toString());
    }

- sunilsurana1986 October 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think I have a good solution with O(N) complexity.

String findSmallestDistinctLex(String str) {
			TreeMap<Character, List<Integer>> charMap = new TreeMap();
			for (int i = 0; i < str.length(); i++) {
				char c = str.charAt(i);
				List<Integer> indexes = (charMap.containsKey(c)) ? charMap.get(c) : new ArrayList<Integer>();
				indexes.add(i);
				charMap.put(c, indexes);
			}

			Map.Entry<Character, List<Integer>> firstEntry = charMap.pollFirstEntry();
			char lexStart = firstEntry.getKey();
			int indexStart = firstEntry.getValue().get(0);

			TreeMap<Integer, Character> indexMap = new TreeMap<Integer, Character>();
			indexMap.put(indexStart, lexStart);

			for (char c : charMap.keySet()) {
				List<Integer> indexes = charMap.get(c);
				int nextIndex = -1;
				for (int index : indexes) {
					if (index > indexStart) {
						nextIndex = index;
						break;
					}
				}
				if (nextIndex == -1) {
					nextIndex = indexes.get(indexes.size() - 1);
				}
				System.out.println(nextIndex + " char: " + c);
				indexMap.put(nextIndex, c);
			}

			StringBuilder sb = new StringBuilder();
			for (int i : indexMap.keySet()) {
				sb.append(indexMap.get(i));
			}
			return sb.toString();
		}

- Omar February 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think I have O(N) solution.

String findSmallestDistinctLex(String str) {
			TreeMap<Character, List<Integer>> charMap = new TreeMap();
			for (int i = 0; i < str.length(); i++) {
				char c = str.charAt(i);
				List<Integer> indexes = (charMap.containsKey(c)) ? charMap.get(c) : new ArrayList<Integer>();
				indexes.add(i);
				charMap.put(c, indexes);
			}

			Map.Entry<Character, List<Integer>> firstEntry = charMap.pollFirstEntry();
			char lexStart = firstEntry.getKey();
			int indexStart = firstEntry.getValue().get(0);

			TreeMap<Integer, Character> indexMap = new TreeMap<Integer, Character>();
			indexMap.put(indexStart, lexStart);

			for (char c : charMap.keySet()) {
				List<Integer> indexes = charMap.get(c);
				int nextIndex = -1;
				for (int index : indexes) {
					if (index > indexStart) {
						nextIndex = index;
						break;
					}
				}
				if (nextIndex == -1) {
					nextIndex = indexes.get(indexes.size() - 1);
				}
				System.out.println(nextIndex + " char: " + c);
				indexMap.put(nextIndex, c);
			}

			StringBuilder sb = new StringBuilder();
			for (int i : indexMap.keySet()) {
				sb.append(indexMap.get(i));
			}
			return sb.toString();
		}

- Omar February 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

You can do a first pass on the string and index all of the characters in a dictionary.

ex)

cbacdcbc -> 'a':[2], 'b':[1,6], 'c':[0,3,5,7], 'd':[4]

On the second pass, pull the least index of each character and save the string formed by combining the characters at those indices. Then, continually remove the least index from that string and replace it with the next instance of that character and repeat until all characters have been used. Compare the new string every time to the current lexicographically least string.

ex)

cbacdcbc -> 'a':[2], 'b':[1,6], 'c':[0,3,5,7], 'd':[4]

[2,1,0,4] -> cbad
V
[2,1,3,4] -> bacd
V
[2,6,3,4] -> acdb
V
[2,6,5,4] -> adcb
V
[2,6,7,4] -> adbc

The complexity here is O(n), since it does 2 passes, and each pass only looks at each index once. Since the problem is restricted to only 26 characters, the complexity of finding the minimum index on each pass in the second half can be treated as O(1)

- Alex September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

hmm, I'm wondering how is it O(n) since combining characters is also O(n) then the complexity would be O(n^2).

- justaguy September 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Combining characters will take max of 26 lookups in the second single loop, there by constant!!

- Anonymous September 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

makes sense. Its a good solution.

- justaguy September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

This doesn't work for abcadaba. Your solution ends up with cdba, while the correction solution is abcd.

- Anonymous September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This solution does not work on acbac.

- rex321 September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution does not work for acbac

- rex321 September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how did [2,1,0,4] -> cbad happen in the second iteration?

- Anonymous September 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how did this happen [2,1,0,4] -> cbad in the second pass first iteration?

- derikd September 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We can create a binary search tree. Since the binary search tree does not contain the duplicate and also the inorder traversal can print the element in lexical order.

- Anonymous September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You'll destroy the input "cba" into "abc".

- Santoso.Wijaya September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

My previous solution was a miss, and maybe a bit complicated. But I really like Krutin's idea to iterate backwards on the input. So here is the implementation of that solution in python. Let me know if this works or not. Thanks.

s = 'cbacdcbc'

seen = dict()
a = list(s)

for i in reversed(range(len(a))):
    if a[i] in seen:
        if a[i+1] < a[i]:
            a[i] = ''
        else:
            a[seen[a[i]]] = ''
            seen[a[i]] = i
    else:
        seen[a[i]] = i

print ''.join(a)

- linteanm September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you could not pass the case in my ps.

- lxfuhuo September 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

C++ solution in O(N)

#include <iostream>
#include <string>

using namespace std;

int main()
{
	string in;
	cout<<"Input a string:"<<endl;
	cin>>in;
	cout<<endl;
	
	int arr[26];
	
	for (int i = 0; i < 26 ; i++)
	{
		arr[i] = 0;
	}
	
	for (int i = 0; i < in.size(); i++)
	{
		unsigned char index = in[i] - 'a';
		if(index < 0 || index > 25)
		{	
			cout<<"error input";
			return 1;
		}
		arr[index] = 1;
	}
	
	for (int i = 0; i < 26 ; i++)
	{
		if(arr[i] == 1)
		{
			cout<<(char) (i + 'a');
		}
	}
	
	return 0;
}

- cdhsiung September 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Input: "cbac"

Your program will output: "abc", which is not correct.

- Santoso.Wijaya September 12, 2015 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More