## 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;
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;//positions of each character
int lastPos={-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;
}``````

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

magic, it works

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.

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 :)

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

It is really cool ! Thanks a lot!

Comment hidden because of low score. Click to expand.
0
of 0 votes

How are you removing c from bacdbcb?

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.

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.

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; // 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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.

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``````

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.

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``````

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.

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.

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 ?

Comment hidden because of low score. Click to expand.
0
of 0 votes

you could get the conception form wiki~

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 = {0};
char* forwardProbe = argv;
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? *rearProbe < *forwardProbe
: *(rearProbe -1) < *forwardProbe) )
{
*rearProbe = *forwardProbe;
rearProbe++;
hist[*forwardProbe - 'a'] = 0;
} else {
hist[*forwardProbe - 'a']--;
}
break;
}
forwardProbe++;
}
*rearProbe = '\0';
printf("%s\n", argv);
return EXIT_SUCCESS;
}``````

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?

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 = {0};
char* forwardProbe = argv;
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? *rearProbe < *forwardProbe
: *(rearProbe -1) < *forwardProbe) )
{
*rearProbe = *forwardProbe;
rearProbe++;
hist[*forwardProbe - 'a'] = 0;
} else {
hist[*forwardProbe - 'a']--;
}
break;
}
forwardProbe++;
}
*rearProbe = '\0';
printf("%s\n", argv);
return EXIT_SUCCESS;
}``````

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;
}
}``````

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

Correct answer for "cbacdcbca" is "acdb".

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>;
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;
}
}``````

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??

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];
}``````

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;
}``````

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}.

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!

Comment hidden because of low score. Click to expand.
0
of 0 votes

Never mind, can is right, just tested.

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".

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;

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;
}``````

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?

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".

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 :(

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".

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``````

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.

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;

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, take a look at my post

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 = {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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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();
}``````

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();
}``````

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

Comment hidden because of low score. Click to expand.
0
of 0 votes

bcabc, your solutions returns wrong answer

Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution is wrong

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();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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?

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?

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();
}``````

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.

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;
}``````

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);
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"));

}

}``````

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)

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);
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"));

}

}``````

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);
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"));

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

Test

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

Test

``System.out.println("hello");``

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')``````

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);
}
}``````

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;

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;
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;
}
}``````

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)``````

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)``````

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)
return ''.join([k for k in v])``````

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

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;
}``````

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)
{
int i=0;
while(str[i]!='\0')
{
dictionary[str[i]-'a']++;
i++;
}
}

char* removeDuplicates(char *str,int dictionary)
{
char *result=new char[strlen(str)];
for(int k=0;str[k]!='\0';k++)
{
for(int i='a';i<='z';i++)
{
int tempDict={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={0};
createDictionary(str,dictionary);

char *result=removeDuplicates(str,dictionary);
cout<<result;
return 0;
}``````

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

``````removedup(char* input)
{
int a;

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;
}

}``````

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
}

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.

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

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.

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;
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';
}``````

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;
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;
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;
}``````

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'. 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={-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)

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

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 array.
1.1 if the index value in int 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 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;
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]);
}``````

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;

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());
}``````

}

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;
int[] pos=new int;
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;

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());
}
}

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();
}
}``````

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.

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());
}``````

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();
}``````

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();
}``````

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':, 'b':[1,6], 'c':[0,3,5,7], 'd':

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':, 'b':[1,6], 'c':[0,3,5,7], 'd':

[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)

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).

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!!

Comment hidden because of low score. Click to expand.
0
of 0 votes

makes sense. Its a good solution.

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.

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

This solution does not work on acbac.

Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution does not work for acbac

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?

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?

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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)``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

you could not pass the case in my ps.

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;

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

Input: "cbac"

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

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