CareerCup

The problem is same as finding the smallest window containing all the characters of a given string (here its 'ab'). If such a window is there return 'true'. Provide any alternate soln if there.

Given an input string A and the template string B, first use quicksort to sort B into B', and first |B| elements in A denoted as C; dynamically move C along A, each time the 1st element in C is removed and the next char is appended into C, just like insertion sort to sort C into C' and match C' == B'

Here is my thought: For the permutation of string, its simplified represents is the number of each character existed in the string. If you want to check if A's permutation is sub string of the B string, you only need to be sure that the number of each kind of character in A is less the number of the same character in the string B. So you can build a histogram of characters in A by going through A, then going through B, decrease the count of character histogram of A when it find the one in B. Return true when all histogram reach zero during the going through B, otherwise return false.

here is the code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int compare(const void *a,const void * b)
{
    return (*(char*)a-*(char*)b);
}
int main()
{
char str[]="aabcdefgh";
char b[]="ba";
char c[10];
qsort(b,strlen(b),sizeof(char),compare);
int p=strlen(str);
int l=strlen(b);
int k,m;
for(int i=0;i<=p-l;i++)
{
    m=0;
    for(int j=i;j<i+l;j++)
    {c[m++]=str[j];
    
    }
    qsort(c,l,sizeof(char),compare);
    cout<<endl;
    for(k=0;k<l;k++)
    {   if(c[k]!=b[k]) break;  }
    if(k==l)
    cout<<"string is found at location i=  "<<i;
}
return 0;
}

- take each character in smaller string and add its position in larger string into sorted array
- if all chars are there in larger string, check if all the position is in sequence

Eg
String a = abcdefghij
String = dcfe

Sorted positions will be 3 4 5 6 so will return true

I am assuming it should return false for above case since lookalike question is a specific permutation of smaller string must be sub string of larger string

yaker no that question is different

public static bool isubstring(string S1, string S2)
{
int sumS1 = 0;
int sumS2 = 0;

for (int i = 0; i < S2.Length; i++)
{
sumS2 += (int)S2[i];
}
for (int i = 0; i < S1.Length - S2.Length + 1; i++)
{
int index = i;
sumS1 = 0;
for (int j = 0; j < S2.Length; j++)
{
sumS1 += (int)S1[index];
index++;
}
if (sumS1 == sumS2)
return true;
}
return false;

}

get a element from string A, search for that in string B1(Copy of second string B),If we dont find it go to next element in A.
If we find element at position 'i' in B1, replace that element with 0 in B1(we did not modify anything in B).
search for the next element in A in B1 and replace that element with 0 in B1 till we could not find the a .elements of A in B1 or all elements in B1 are 0.
if all elements in B are 0.result is success.

if we could not find a element at position k of A in B1. get refresh B1 i.e copy from B.
now find for that element in B(the original string) if we could not find it in B, Continue to repeate the same steps from position k+1 .
if you find it in B,repeate steps from position i+1

To solve this problem.. First find the maximum window in which all the character of given pattern is present. If max window length is equal to pattern length than it is going to be the permutation of given string other wise not.Code is given below let me know if it fails in any scenario it is working for me for test cases i think of.

int FindpatLen(char *str,char *pat)
{
if(!*str)
return 0;
int len1=strlen(str),len2=strlen(pat),count=0;
int hasfound[26]={0},needtofound[26]={0};
int i=0,begin=0,max=999;
for(i=0;i<len2;i++)
needtofound[pat[i]-97]++;
i=0;
for(;i<len1;i++)
{
if(needtofound[str[i]-97]==0)
continue;
hasfound[str[i]-97]++;
if(hasfound[str[i]-97]<=needtofound[str[i]-97])
count++;
if(count==len2)
{
while((needtofound[str[begin]-97]==0) || (hasfound[str[begin]-97]>needtofound[str[begin]-97]))
{
if(hasfound[str[begin]-97]>needtofound[str[begin]-97])
hasfound[str[begin]-97]--;
begin++;
}
if(max>(i-begin))
max=i-begin+1;
}
}
return max;
}
bool Ispermutation(char *str,char *pat)
{
int len=strlen(pat);
if(len==FindpatLen(str,pat))
return true;
return false;
}
int main()
{
char str[]="abcabcabc";
char pat[]="cab";
bool res=Ispermutation(str,pat);
getchar();
return 0;
}

1.Create a temporary bitMap of <character,Bit> initialize them with character and bit value 0
2. Scan through the big array when you find a character in the small array update the bit map with the char and set it to 1 if the character bit has 0.

public static boolean checkPresence(char[] arr, char[] temp) {

int track = 0;
Map<Character, Integer> tempMap = new HashMap<Character, Integer>();
for (char c : temp) {
tempMap.put(c, 0);
}
int prev = 0;
for (int i = 0; i < arr.length; i++) {
char c = arr[i];
if (tempMap.get(c) != null && tempMap.get(c) == 0
&& (prev == 0 || prev == i - 1)) {
tempMap.put(c, 1);
track++;
prev = i;
}
}
return track == temp.length ? true : false;
}



Let me know if i miss any case

If long string has length n and the short has length m
Best complexity I reached:
-Assuming no repeated characters in either string >> O(n)
-Allow repeated characters in the long string >> O(n) too
-Allow repeated characters in either string >> O(n*log m)

Firstly, Sort the string and substring separately。Time complexity is O(sqrt(n))
Secondly, use match algorithm on the ordered string。Time complexity is O(n)
so the total complexity is O(n).

package com.santosh.career;

import java.util.HashMap;
import java.util.Map;

public class Career15555796 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		char[] small = { 'c', 'b' };
		char[] big = { 'g', 'b', 'a', 'c', 'd', 'e' };
		Map<Character, Integer> charMap = new HashMap<Character, Integer>(26);
		Map<Character, Integer> fixedCharMap = new HashMap<Character, Integer>(
				26);
		resetCharMap(small, charMap);
		resetCharMap(small, fixedCharMap);
		int smallCount = small.length;
		int flag = 0;
		for (char c : big) {
			if (charMap.get(c) != null) {
				charMap.put(c, charMap.get(c) - 1);
				flag = 1;
				smallCount--;
			}
			if(smallCount==0){
				System.out.println("Found a match");
				break;
			}
			if (flag == 1 && charMap.get(c) == null) {
				charMap = fixedCharMap;
				flag = 0;
				smallCount = small.length;
			}
		}
	}

	private static void resetCharMap(char[] small,
			Map<Character, Integer> charMap) {
		for (char c : small) {
			if (charMap.get(c) == null) {
				charMap.put(c, 1);
			} else {
				charMap.put(c, charMap.get(c));
			}
		}
	}
}

The Algorithm i posted above its O(n) and i am using two constant size arrays.
I handled all cases i suppose let me know if it fails in any case

package questions;

import java.util.Arrays;

public class HasPerm {
	public static void main(String[] args) {
		System.out.println(hasPerm("abcdefg", "ba"));
		System.out.println(hasPerm("abcdefg", "gf"));
		System.out.println(hasPerm("abcdefg", "dc"));
	}

	public static boolean hasPerm(String source, String find) {
		String k = key(find);
		for (int i = 0; (i + find.length()) <= source.length(); ++i) {
			String sub = source.substring(i, i + find.length());
			if (key(sub).equals(k))
				return true;
		}

		return false;
	}

	private static String key(String s) {
		char[] ary = s.toCharArray();
		Arrays.sort(ary);
		return new String(ary);
	}
}

How about this, you just sort both the strings and then compare the index of the smaller string in the larger string. If it is -1, then the smaller string is not a part of the larger string.

import java.util.*;
public class sort {
	public static void main(String args[])
	{
		String str1 = "abcdefgh";
		String str2 = "fed";
		char a[] = str1.toCharArray();
		Arrays.sort(a);
		String new_str_1 = new String(a);
		System.out.println(new_str_1);
		char b[] = str2.toCharArray();
		Arrays.sort(b);
		String new_str_2 = new String(b);
		System.out.println(new_str_2);
		if(new_str_1.indexOf(new_str_2) != -1)
		{
			System.out.println("True");
		}
		else
		{
			System.out.println("False");
		}
	}

}

sort is not required, i think

reverse the second string and use kmp search will be better. and also we can use suffix tree or suffix array, but they are too complicated. here is my program, and it will take O(n) time complexity(n: the length of first string) and O(m) space complexity(m: the length of second string):

#include<iostream>
#include<string>
using namespace std;

void swap(char *a, char *b) {
	char temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

void reverse(char *p_start, char *p_end) {
	while(p_start < p_end) {
		swap(p_start, p_end);
		p_start++;
		p_end--;
	}
}

void get_next(char *p, int len, int *next) {
	int j = -1;
	int i = 0;
	next[i] = -1;
	while(i < len - 1) {
		if(j == -1 || p[i] == p[j]) {
			++i;
			++j;
			if(p[i] != p[j])
				next[i] = j;
			else
				next[i] = next[j];
		} else {
			j = next[j];
		}
	}
}

char *kmp_search(char *s, int s_len, char *p, int p_len) {
	if(NULL == s || NULL == p || 0 == s_len || 0 == p_len)
		return NULL;
	int *next = (int*)malloc(sizeof(int) * p_len);
	memset(next, 0, sizeof(int) * p_len);
	get_next(p, p_len, next);
	int i = 0; 
	int j = 0;
	while(i < s_len && j < p_len) {
		if(j == -1 || s[i] == p[j]) {
			++i;
			++j;
		} else {
			j = next[j];
		}
	}
	if(next)
		free(next);
	if(j >= p_len)
		return s + i - p_len;
	else
		return NULL;
}

int is_contain_permutation(char *s, char *d) {
	if(NULL == s || NULL == d)
		return 0;
	int s_len = strlen(s);
	int d_len = strlen(d);
	char *temp = (char*)malloc(d_len + 1);
	strcpy(temp, d);
	reverse(temp, temp + d_len - 1);
	char *ret = kmp_search(s, s_len, temp, d_len);
	if(temp)
		free(temp);
	if(ret)
		return 1;
	else 
		return 0;
}

int main(int argc, char *argv[]) {
	char s[] = "abcdefg";
	char d[] = "ba";
	is_contain_permutation(s, d);
	cin.get();
	return 0;
}

int[] count = new int[256];
for(char c: str1.toCharArray())
++count[c];
for(char c: str2.toCharArray())
{
if(count[c]==0)
return false;
}
return true;

I think of hashing all the characters into the hashtable and maintain the count. Then, for every character in S2, check if it exists in the hashtable. if so, then result is true. it takes o(n) where n is the size of the longest string.

This idea is not based on the order and it depends whether there exists every character of a string exists in the original string. When it exists, the permutation is possible (obviously)

will this idea work pls correct me if I am wrong:)
1.create two hash tables one for string 1 and another for string 2
2.if the hash values of string 2 if it is contained within string 1 then string is accepted....

How about this:

p1 = &Array1;
strcpy(Array3, Array2);
while (*p1 != '\0')
{
for (i = (p1 - Array1); i < ((p1-Array1) + strlen(Array2)); i++)
{
for (j = 0; j < strlen(Array2); j++)
{
if (Array1[i] == Array2[j])
{
Array2[j] = 'x';
count++;
break;
}
}
}
if(count == strlen(Array2))
{
success = 1;
break;
}
else
{
p1++;
strcpy(Array2, Array3);
count = 0;
}
}

if (success == 1)
{
printf("Success");
}
else
{
printf("Failure");
}

Check if a substring permutation exists in a string

Check if a substring permutation exists in a string. Ex. A = “most random” B = “mod”

So the function should return true since “mod” a permutation of “dom” exists in string A

—————————————————————————————————————–

// Have this as class field to expose to multiple methods
private Hashtable mTable;public bool SubStringExistsAsPermutation(string A, string B)

{
if (String.IsNullOrEmpty(A))
{
throw new ArgumentException(“A cannot be null”);
}
if (String.IsNullOrEmpty(B))
{
throw new ArgumentException(“B cannot be null”);
}

mTable = new Hashtable();

// Fill hashtable with B string
foreach (char ch in B)
{
mTable[ch] = Convert.ToInt32(mTable[ch]) + 1;
}

// Read each character from String A. Keep comparing it with hashtable characters
// If character in A is not found in hashtable, keep moving A pointer
// If character in A is found in hashtable, Set a flag LookForConsecutiveCharacter = true
// If you find LookForConsecutiveCharacter = true, and next character is not found Then –
// Set LookForConsecutiveCharacter = false and reset hashmap to its initial state to look for next pattern ahead

bool LookForConsecutiveCharacter = false;
int count = 0;

foreach(char ch in A)
{

if (count == B.Length)

{
break;
}

if (Convert.ToInt32(mTable[ch]) >= 1)
{
mTable[ch] = Convert.ToInt32(mTable[ch]) – 1;
LookForConsecutiveCharacter = true;
count++;
}
else
{
// If we expected consecutive characters for permutation and its not found, reset hashtable
if (LookForConsecutiveCharacter)
{
ResetHashTableToDefault(B);
LookForConsecutiveCharacter = false;
count = 0;
}
}
}

// Verify if we found permutation
bool permutationFound = true;
foreach (char key in mTable.Keys)
{
if (Convert.ToInt32(mTable[key]) != 0)
{
permutationFound = true;
break;
}
}
return permutationFound;
}

private void ResetHashTableToDefault(string B)
{
mTable.Clear();
foreach (char key in B)
{
mTable[key] = Convert.ToInt32(mTable[key]) + 1;
}
}

bool find_permutation(const string& str, const string& other)
{
	string sorted;
	sort(other, sorted); //O(nlogn)
	
	for(int i = 0; i < str.length(); ++i)
	{
		if(i + sorted.length() < str.length())
		{
			string subs = str.substr(i, sorted.length());
			string sortedSub;
			sort(subs, sortedSub); //O(klogk)
			if(sortedSub == sorted) return true;
		}	
	}	
	
	return false;
}

We can do this in O(n). The algorithm is simple, we move a window of |p| from left to right, and keep a counter of characters passed. We also update a counter d whenever a match
between the moving counter and histogram of p happens or otherwise.

def persub(s, p):
    pc = Counter(p)
    cc = Counter()
    d = 0
    for i, c in enumerate(s):
        _cc = cc.get(c, 0)
        if c in pc and _cc == pc[c]:
            d -= 1
        cc[c] = _cc + 1
        if cc[c] == pc[c]:
            d += 1
            
        if i >= len(p):
            _c = s[i - len(p)]
            _cc = cc.get(_c, 0)
            if _c in pc and _cc == pc[_c]:
                d -= 1
            cc[_c] = _cc - 1
            if cc[_c] == pc[_c]:
                d += 1
        
        if d == len(pc):
            yield i - len(p) + 1

Guys we need to find a substring of string 1 which consists of only characters of string2 and has same length as string 2, once while iterating you find such a substring then compare the count of each character in the substring and string 2 , if string 2 has all unique characters this
problem becomes simply finding the longest substring in string 1 that consists of all unique characters , characters here being those of string 2 , then if the length of this longest substring equals length of string 2 , then this is the code

i m posting the c code

#include<stdio.h>
#include<iostream>
using namespace std;

void printallpermutations(char* a , char* b)
{
   int i;

   bool aux[26]={0};
   int visited[26]={-1};
   int current_substring_begin=0;
   int max_substring_len=0;
   int max_substring_begin=0;
   for(int i=0;b[i]!='\0';++i)aux[b[i]]=1;

   while(a[current_substring_begin]!='\0')
   {

   while(b[a[i]]==0)i++;

   count=0;
   //first char encountered

   current_substring_begin=i;
   while(b[a[i]])
   {
       if(visited[a[i]]==-1){
           visited[a[i]]=i;
           count++;
       }

       else{
       //it occurs but has previous occurence , if previous occurence is after current begin, then its a duplicate within current substring
       //and the current unique substring ends one char before this char and the new begins after the previous visited val

       if(visited[a[i]]>=current_substring_begin)
       {
           //substring ends
           if(count>max_substring_len){
               max_substring_len=count;
               max_substring_begin=current_substring_begin;
               current_substring_begin=visited[a[i]]+1;//start from next char since last visit
       }

       }
}
   }


}

if(max_substring_len==strlen(b)){
cout<<"contains";
for(int p=max_substring_begin;p<max_substring_begin+max_substring_len;++p)cout<<a[p];

}

else cout<<"doesnot contains";
return;
}


int  main()
{
    char a[] = "abcdnmpbacdmnpccc";
    char b[] = "pmn";

    printallpermutations(a,b);


    return 0;
}

Please check out this generic solution, that will work on all cases, even if the text is not sorted.
we create all possible permutations of a pattern and then simply compare.

class P13
{
	static String text;
	static boolean result = false;
	public static void main(String[] args) 
	{
		text = "badfcge";
		String patt = "fcd";
		permutations(patt);
		System.out.println(result);
	}
	
	public static void permutations(String patt)
	{
		permutations("",patt);
	}
	
	public static void permutations(String prefix, String patt)
	{
		int l = patt.length();
		if(l == 0)
		{
			//System.out.println(prefix);
			if(search(text, prefix))
				result = true;
		}
		for(int i=0;i<l;i++)
			permutations(prefix+patt.charAt(i), patt.substring(0, i)+patt.substring(i+1, l));
	}
	
	
	public static boolean search(String text, String pattern)
	{
	
		for(int i=0;i<text.length()-pattern.length();i++)
		{
			int x = i;
			int count = 0;
			for(int j=0;j<pattern.length();j++,x++)
			{
				if(text.charAt(x) == pattern.charAt(j))
					count++;
			}
			if(count == pattern.length())
				return true;
		}
		return false;
	}
}

class P13
{
	static String text;
	static boolean result = false;
	public static void main(String[] args) 
	{
		text = "badfcge";
		String patt = "fcd";
		permutations(patt);
		System.out.println(result);
	}
	
	public static void permutations(String patt)
	{
		permutations("",patt);
	}
	
	public static void permutations(String prefix, String patt)
	{
		int l = patt.length();
		if(l == 0)
		{
			//System.out.println(prefix);
			if(search(text, prefix))
				result = true;
		}
		for(int i=0;i<l;i++)
			permutations(prefix+patt.charAt(i), patt.substring(0, i)+patt.substring(i+1, l));
	}
	
	
	public static boolean search(String text, String pattern)
	{
	
		for(int i=0;i<text.length()-pattern.length();i++)
		{
			int x = i;
			int count = 0;
			for(int j=0;j<pattern.length();j++,x++)
			{
				if(text.charAt(x) == pattern.charAt(j))
					count++;
			}
			if(count == pattern.length())
				return true;
		}
		return false;
	}

}

An easy solution assuming alphabets from 'a' to 'z' allowed.
Time O(N)
Space O(1)

bool isSubstr(string s, string sub)
{
	int l1 = s.length();
	int l2 = sub.length();
	if(l2 > l1)	
		return false;
	string alpha2 = "00000000000000000000000000";
	string alpha1 = "00000000000000000000000000";
	for(int i = 0;i < l2;i++)
	{
		alpha1[sub[i] - 'a']++;
		alpha2[s[i]-'a']++;
	}
	if(alpha2 == alpha1)
		return true;
	for(int i = 1;i +l2  < l1;i++)
	{	
		printf("here\n");
		alpha2[s[i-1]-'a']--;
		alpha2[s[i+l2-1]-'a']++;
		if(alpha2 == alpha1)
			return true;
	}
	return false;
}

in python:

#!/usr/bin/python
import itertools

s="abcdefg"
s2="ed"
l=list(itertools.permutations(s2))

for i in l :
    s3="".join(i)
    
    if s.find(s3)!=-1 :
        print("%s occurs in %s" % (s3,s))

C++ solution is below. Only one inefficiency: you need to repopulate the hash every time you don't have match.

int StrLen(char *s)
{
    int length = 0;

    if (s)
    {
        while (*s)
        {
            length++;
            s++;
        }
    }

    return length;
}

void InitHash(int *hash, int hashSize, char *s)
{
    if (hash && s)
    {
        for (int i = 0; i < hashSize; hash[i++] = 0);

        while (*s)
        {
            hash[*s] += 1;
            s++;
        }
    }
}

bool FindPermutation(char *str1, char *str2)
{
    bool found = false;
    int length2 = -1;
    int i = -1;
    int hash[256];

    if (str1 && str2)
    {
        length2 = StrLen(str2);
        InitHash(hash, 256, str2);

        while (*str1)
        {
            for (i = 0; i < length2 && str1[i] != '\0'; i++)
            {
                if (hash[str1[i]] != 0)
                {
                    hash[str1[i]]--;
                }
                else
                {
                    break;
                }
            }

            if (i == length2 || str1[i] == '\0')
            {
                // permutation is found
                found = (i == length2);
                break;
            }
            else
            {
                str1 += (i + 1);
                InitHash(hash, 256, str2);
            }
        }

    }

    return found;
}

#include <iostream>
#include<algorithm>
#include<string>
using namespace std;

int main()
{
    int n;
    cin>>n;
    cin.ignore();
    for(int i=0;i<n;i++)
    {
        string p,t;
        getline(cin,p);
        getline(cin,t);
        int lp=p.length();
        int lt=t.length();
        int fp[26]={0},ft[26]={0};
        for(int i=0;i<lp;i++)
            fp[p[i]-'a']++;
        for(int i=0;i<lp;i++)
            ft[t[i]-'a']++;
        bool m; 
        for(int i=lp;i<=lt;i++)
        {
            m=true;
            for(int j=0;j<26;j++)
                if(fp[j]!=ft[j])
                {
                    m=false;
                    break;
                }
            if(m)
                break;
            ft[t[i-lp]-'a']--;
            ft[t[i]-'a']++;
        }
        if(m)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
    return 0;
}

cracking the coding interview has the same question in chapter 1

convert two arrays to numbers

S1 : abcdefg -------> 01234567
S2 : ba -------> 10
int sumS1 = 0;
int sumS2 = 0;

for(int i = 0;i<S.length;i++)
{
sumS2+=S2[i];
}
for(int i = 0;i<S1.length - S2.length + 1; i++)
{
if(S1[i] + S1[i+1] == sumS2)
return true;
}

Compute all the permutations of the smaller string(easily done recursively). For each permutation, check if it is a substring of bigger string.

public static void main(String[] args) throws Exception
	{
		String one = "abcdefg";
	
		String two = "ba";
		

		System.out.println(findifsubperumuation(one, two));

	
	}
	
	
	//Assumes one is longer than 2
	public static boolean findifsubperumuation(String one, String two)
	{
		
		
		
		int k = two.length();
		
		ArrayList<String> all;
		for(int i=0; i<one.length() && i+k<one.length()+1; i++)
		{
			String current = one.substring(i, i+k);
			all=permutation(current);
			for(String perm : all)
			{
				if(perm.equals(two))
				{
					return true;
				}
			}
			
		}
		
		
		
		return false;
	}

	public static ArrayList<String> permutation(String s)
	{
		

		if(s.length()==1)
		{

			ArrayList<String> perms = new ArrayList<String>();
			perms.add(s);
			return perms;
		}
		
		
		
		ArrayList<String> permsother = permutation(s.substring(1));
			
		ArrayList<String> perms = new ArrayList<String>();
	
	
		String firstletter = s.substring(0,1);
		
		for(String current : permsother)
		{
			for(int i=0; i<=current.length(); i++)
			{
			
				String Firstpart = current.substring(0,i);
				String Secondpart = current.substring(i);
				String together = Firstpart.concat(firstletter);
				together=together.concat(Secondpart);
				perms.add(together);
				
		
			}
			
			
		}
		
		
		
		return perms;
		
	}

HI i think this can be easily solved by Hash maps.
Create a hash map for the second string and keep incrementing for a new instance found for a letter. ex: abdds: a(1),b(1),d(2),s(1).
Then for the second string, keep decrementing if the same letter is found.
if the first string ends and all the letters have the values associtaed to them as zeroes: return TRUE.
The complexity is m+n, 1.e. of O(m)

Sort both string and then do substring search.