Siva
BAN USERO(n) solution..
static int numberOfSubstrings(String input) {
int count = 0;
int mode = 3; //ternary
boolean[] isInSubString = new boolean[mode];
initArray(isInSubString);
int subStringStart = 0;
int[] lastIndexOfCharInSubString = new int[mode];
for(int i = 0; i < input.length(); i++){
boolean b = isInSubString[input.charAt(i) -'a'];
int j = input.charAt(i) - 'a';
if(b == false){
isInSubString[j] = true;
lastIndexOfCharInSubString[j] = i;
}else{
lastIndexOfCharInSubString[j] = i;
}
if (doAllCharactersInSubString(isInSubString)) {
if (subStringStart == 0) {
int n = i - subStringStart;
count += n * (n+1)/2;
}
char charAt = input.charAt(subStringStart);
while (!(lastIndexOfCharInSubString[charAt - 'a'] == subStringStart)) {
subStringStart++;
charAt = input.charAt(subStringStart);
}
char removedChar = input.charAt(subStringStart);
isInSubString[removedChar - 'a'] = false;
subStringStart = subStringStart + 1;
count += i - subStringStart + 1;
} else if (count > 0) {
count += i - subStringStart + 1;
}
}
return count;
}
private static boolean doAllCharactersInSubString(boolean[] isInSubString) {
for (boolean b : isInSubString) {
if(b == false)
return false;
}
return true;
}
private static void initArray(boolean[] isInSubString) {
isInSubString[0] = false;
isInSubString[1] = false;
isInSubString[2] = false;
}
in the second step. you are trying to do a binary search for the number. While doing binary search , one has to count the number of times right subtree is called from root to the number. this gives you number of elements in the right sub array that are greater than the current number
- Siva July 07, 2012here is O(n) solution
1.for each entry in the array,
-> look up in hashmap for the value(parent)
if there is an entry add the child(index) to it and add child to hashmap
else
create one entry for the value(parent) and add child(index) to it and add both to
hashmap
At the end you end up with n-ary tree. Now calculate depth of it O(n).
I am not sure about linear but you can do it O(nlogn)
1.traverse from back and construct a binary search tree.
2. for each number in the array .. find it in binary search tree keeping count of number of right calls(In binary search tree depending on the condition , we make one of the two calls (left or right) ;add this count to sum
3. after the iteration of the array. sum is the answer
private static String input;
private static void generateCombinations(String string) {
input = string;
_generateCombinations("", 0, true);
}
private static void _generateCombinations(String currentString,
int currentIndex, boolean print){
if(currentIndex >= input.length()){
if(print)
System.out.println(currentString);
return;
}
if(print)
System.out.println(currentString);
_generateCombinations(currentString + input.charAt(currentIndex), currentIndex + 1, true);
_generateCombinations(currentString, currentIndex + 1, false);
}
I think a BST will do this.
If for any interval.. if you have to add a range starting number on left of some node and range ending number on right of some node and viceversa.. then they are overlapping..
If they are not overlapping... both number should fall at the same place(or you can say.. distance between the interval numbers should be zero after you have inserted into BST)
even though this uses a single arraylist, it does not mean that this is space efficient.
If you compare two stack implementation and this implementation,
you can see at all stages , both implementations uses the same memory.
More over, since this implementation takes little more time than the other, as it removes elements from one index to another.
and the implementation of two stacks.. is easier to read and implement
RepTaylahMacge, Consultant at Accenture
Assigned to manage the requirements of foreign clients specifically those from the Chinese, Arabic, and French-speaking markets.I am passionate ...
Repsamuelcsmith700, Accountant at Absolute Softech Ltd
Je suis chef d'équipe de support Office dans une entreprise Action Auto. Je suis également rédacteur de blog. J ...
Repmelonydmaxwell, maintenence engineer at AMD
Hi, I am working as a health information technician and my work is to collect and maintain a patient's ...
Repalinehchavez, SHOT 1500 NIGHT 5000 Call girls in Munirka Metro 9711794795 at Apple
Hi, I am Aline From New York USA. I am working as a Real estate rental agent in an Energy ...
Repjunehudson, Associate at Advisory Board Company
I am passionate about fashion and love to explore black magic to take revenge.Being a fashion designer involves more ...
Repjimmybdepuy, Front-end Software Engineer at Arista Networks
Hi, I am Jimmy from los Angeles. I am a painter. I have Knowledge of different types and shades of ...
Repkennypmillerk, AT&T Customer service email at 247quickbookshelp
My name is Kenny and I am working as a trusted investor in Pittsburgh USA.I identify / set up a ...
Repsusiejcrider, Member Technical Staff at Accolite software
I was a Communications Consultant with experience in working across various clients .technology, consumer, hospitality, financial services and corporate social ...
This is no binary search. Ur algo is O(n) if there is only 1 at the last index
- Siva May 22, 2013