UB
BAN USERIMHO solving this algo with an extra space is relatively easier. So I have tried to implement the solution with modifying the given string(although this constraint doesn't seem to be given in the problem statement). Here's the sample code:
private static String countLetters(StringBuilder str){
StringBuilder str2 = new StringBuilder();
int count = 1, position = 1;
for (int i = 0; i < str.length() - 1 ; i++) {
if(str.charAt(i) == str.charAt(i+1)){
count++;
}
else{
StringBuilder temp = new StringBuilder();
temp.append(count);
temp.append(str.charAt(i+1));
str.insert(position, temp);
i += 2;
position += 2;
count = 1;
}
}
str.insert(position++, count);
str.delete(position, str.length());
return str.toString();
}
Saving it in a temporary DS(in this case, hashmap) and comparing against it for every new char.
private static String findFirstRepeatingChar(String str){
Map<String, Integer> hash= new HashMap<String, Integer>();
for (int i = 0; i < str.length(); i++) {
String temp = str.substring(i, i+1);
if(hash.containsKey(temp))
return temp;
hash.put(temp, 1);
}
return "NOT FOUND";
}
Basic thought here is to store the prime numbers in an array so that for determining any subsequent number say n, we need not do the checking for all n-1 integers instead we can check with only the given prime numbers less than n.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class generatePrimeNumbers {
public static void main(String[] args) {
int position = 1;
int N =40;
int arr[] = new int[N+1];
boolean valFound;
for (int i = 2; i < N; i++) {
valFound = findPrime(i, position, arr);
if(valFound){
arr[position++] = i;
}
}
//we have an array of prime numbers now(arr).
//Below code sorts the array lexicographically.
List<String> list = new ArrayList<String>();
for (int j = 1; j < position; j++) {
list.add(""+arr[j]);
}
Collections.sort(list);
for (String j : list) {
System.out.println(j);
}
}
private static boolean findPrime(int N, int position, int[] arr){
int flag = 0;
for (int i = 2; i < N; i++) {
if(position > 0 && flag == 0){
for (int j = 1; j < position; j++) {
if(N % arr[j] == 0)
return false;
}
flag = 1;
}
}
return true;
}
}
The thought here is to push the left bracket into stack and whenever we encounter a right bracket, pop the entry from stack and compare against the current one.
Time Complexity: O(n)
Auxiliary Space: O(n) for stack
- UB February 10, 2014