Google Interview Question
Backend DevelopersCountry: United States
import java.util.Scanner;
public class Findduplicates {
public static boolean checkRepeat(int array[][], int length, int index, int j, int k){
int i;
for(i=0;i<index;i++){
int x = array[i][j];
if(x>=k)
return true;
}
return false;
}
public static int finddup(String str, int k){
int count=0,c=0;
int length = str.length()+1;
int array[][] = new int[length][length];
int i,j;
for(i=1;i<=length-(2*k)+1;i++){
for(j=i+k;j<length;j++){
char a = str.charAt(i-1);
char b = str.charAt(j-1);
if(a==b){
array[i][j] = array[i-1][j-1]+1;
if(array[i][j] >= k){
if(checkRepeat(array, length, i, j, k)==false)
count ++;
}
}
}
}
return count;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("\n ENter the String: ");
Scanner in = new Scanner(System.in);
String str = in.nextLine();
System.out.println("Enter pattern length: ");
int k = in.nextInt();
System.out.println("String given: "+str+" pattern length: "+k);
int count;
count = finddup(str, k);
System.out.println("count: "+count);
}
}
/*
Time Complexity: O(String size x k size)
Space Complexity: O(String size x k size)
*/
static void printDuplicateStrings(String str, int k) {
if (str == null || str.length() == 0 || k <= 0) {
return;
}
HashMap<String, Integer> substrings = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
StringBuilder aux = new StringBuilder();
if (i <= str.length() - k) {
for (int j = i; j < i + k; j++) {
aux.append(str.toLowerCase().charAt(j));
}
if (!substrings.containsKey(aux.toString())) {
substrings.put(aux.toString(), 1);
} else {
substrings.put(aux.toString(), substrings.get(aux.toString()) + 1);
}
}
}
for (String s : substrings.keySet()) {
if (substrings.get(s) > 1) {
System.out.println(s + " " + substrings.get(s));
}
}
public class Ksubstring {
public static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
System.out.println("Enter the string : ");
String str = in.nextLine();
// in.nextLine();
System.out.println("Enter the value of k : ");
int k = in.nextInt();
if(k>=str.length()) {
System.out.println("Incorrect input!");
return;
}
Map<String,Integer> duplicates = new HashMap<String,Integer>();
for(int i =0 ;i<=str.length()-k;i++) {
String newString = str.substring(i, i+k);
int count = duplicates.containsKey(newString)? duplicates.get(newString) : 0;
duplicates.put(newString, count+1);
// System.out.println(str.substring(i, i+k));
}
for(Map.Entry<String,Integer> me : duplicates.entrySet()) {
if(me.getValue()>1) {
System.out.println(me.getKey());
}
}
}
}
public class Ksubstring {
public static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
System.out.println("Enter the string : ");
String str = in.nextLine();
// in.nextLine();
System.out.println("Enter the value of k : ");
int k = in.nextInt();
if(k>=str.length()) {
System.out.println("Incorrect input!");
return;
}
Map<String,Integer> duplicates = new HashMap<String,Integer>();
for(int i =0 ;i<=str.length()-k;i++) {
String newString = str.substring(i, i+k);
int count = duplicates.containsKey(newString)? duplicates.get(newString) : 0;
duplicates.put(newString, count+1);
// System.out.println(str.substring(i, i+k));
}
for(Map.Entry<String,Integer> me : duplicates.entrySet()) {
if(me.getValue()>1) {
System.out.println(me.getKey());
}
}
}
}
- Roberto January 14, 2018