Google Interview Question Software Developers
Country: -
Interview Type: Phone Interview
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, you're right. It could be applied and make it faster.
I'll update the code.
Thanks :)
@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.
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.
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;
}
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.
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
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.
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
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.
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;
}
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;
}
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;
}
}
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
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;
}
}
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??
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];
}
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;
}
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}.
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!
Tried "cacasc" with krutin's C++ code, and it does NOT produce the correct answer. It outputs "asc" instead of "acs".
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;
}
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?
I think this wont work in all cases. Consider "bcabc" - The algorithm will give us "bac", where as the right solution is "abc".
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 :(
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".
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
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;
}
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;
}
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();
}
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();
}
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();
}
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();
}
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;
}
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"));
}
}
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"));
}
}
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"));
}
}
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')
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);
}
}
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;
}
}
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])
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
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;
}
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;
}
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;
}
}
//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
}
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.
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';
}
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;
}
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)
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]);
}
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());
}
}
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());
}
}
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();
}
}
/**
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.
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());
}
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();
}
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();
}
return_value = []
first_occurance = []
def get_string(str1):
temp_list = list(str1)
for index, i in enumerate(temp_list):
if temp_list.count(i) > 1 and i not in first_occurance:
temp_list.pop(index)
first_occurance.append(i)
get_string(temp_list)
else:
if i not in return_value:
return_value.append(i)
return return_value
return_value = []
first_occurance = []
def get_string(str1):
temp_list = list(str1)
for index, i in enumerate(temp_list):
if temp_list.count(i) > 1 and i not in first_occurance:
temp_list.pop(index)
first_occurance.append(i)
get_string(temp_list)
else:
if i not in return_value:
return_value.append(i)
return return_value
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)
hmm, I'm wondering how is it O(n) since combining characters is also O(n) then the complexity would be O(n^2).
Combining characters will take max of 26 lookups in the second single loop, there by constant!!
This doesn't work for abcadaba. Your solution ends up with cdba, while the correction solution is abcd.
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.
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)
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;
}
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:
- MehrdadAP September 19, 2015string 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; }