Determining if two strings are a substring of a permutation of another String

Question

So I am trying to figure out if two strings when combined together are a substring of a permutation of another string.

I have what I believe to be a working solution but it is failing some of the JUnit test cases and I dont have access to the ones that it is failing on.

here is my code with one test case

String a="tommarvoloriddle";
String b="lord";
String c="voldemort";
String b= b+c; 
char[] w= a.toCharArray();
char[] k= b.toCharArray();
Arrays.sort(k);
Arrays.sort(w);
pw.println(isPermuation(w,k)?"YES":"NO");


static boolean isPermuation(char[] w, char[] k)
{
    boolean found=false;
    for(int i=0; i<k.length; i++)
    {
        for(int j=i; j<w.length; j++)
        {
            if(k[i]==w[j])
            {
                j=w.length;
                found=true;
            }
            else
                found=false;
        }
    }


    return found;
}

any help getting this to always produce the correct answer would be awesome and help making it more efficient would be great too

Answer 1

What you have is not a working solution. However, you don't explain why you thought it might be, so it's hard to figure out what you intended. I will point out that your code updates found unconditionally for each inner loop, so isPermutation() will always return the result of the last comparison (which is certainly not what you want).

You did the right thing in sorting the two arrays in the first place -- this is a classic step which should allow you to efficiently evaluate them in one pass. But then, instead of a single pass, you use a nested loop -- what did you intend here?

A single pass implementation might be something like:

static boolean isPermutation(char[] w, char[] k) {
  int k_idx=0;
  for(w_idx=0; w_idx < w.length; ++w_idx) {
    if(k_idx == k.length)
      return true; // all characters in k are present in w
    if( w[w_idx] > k[k_idx] )
      return false;  // found character in k not present in w
    if( w[w_idx] == k[k_idx] )
      ++k_idx;  // character from k corresponds to character from w
  }
  // any remaining characters in k are not present in w
  return k_idx == k.length;
}

Answer 2

So we are only interested in whether the two combined strings are a subset of a permutation of another string, meaning that the lengths can in fact differ. So let's say we have:

String a = "tommarvoloriddle";
String b = "lord";
String c = "voldemort";

char[] master = a.ToCharArray();
char[] combined = (b + c).ToCharArray();

Arrays.Sort(master);
Arrays.Sort(combined);

System.out.println(IsPermutation(master, combined) ? "YES" : "NO");

Then our method is:

static boolean IsPermutation(char[] masterString, char[] combinedString)
{
    int combinedStringIndex = 0;
    int charsFound = 0;
    int result = 0;

    for (int i = 0; i < masterString.Length; ++i) {
        result = combinedString[combinedStringIndex].CompareTo(masterString[i]);
        if (result == 0) {
            charsFound++;
            combinedStringIndex++;
        }
        else if (result < 0) {
            return false;
        }
    }

    return (charsFound == combinedString.Length);
}

What the above method does: it starts comparing characters of the two strings. If we have a mismatch, that is, the character at the current masterString index does not match the character at the current combinedString index, then we simply look at the next character of masterString and see if that matches. At the end, we tally the total number of characters matched from our combinedString, and, if they are equal to the total number of characters in combinedString (its length), then we have established that it is indeed a permutation of masterString. If at any point, the current character in masterString is numerically greater than the current character in combinedString then it means that we will never be able to match the current character, so we give up. Hope that helps.

Answer 3

If two Strings are a permuation of the other you should be able to do this

public static boolean isPermuted(Strign s1, String s2) {
     if (s1.length() != s2.length()) return false;

     char[] chars1 = s1.toCharArray();
     char[] chars2 = s2.toCharArray();
     Arrays.sort(chars1);
     Arrays.sort(chars2);
     return Arrays.equals(chars1, chars2);
}

This means that when sorted the characters are the same, in the same number.