CODEWITHSUNDEEP
javastringloopsfor-loopsubstring
fallen
fallen

Reputation: 31

Matching subsequence of length 2 (at same index) in two strings

Given 2 strings, a and b, return the number of the positions where they contain the same length 2 substring. For instance a and b is respectively "xxcaazz" and "xxbaaz" yields 3, since the "xx", "aa", and "az" substrings appear in the same place in both strings. What is wrong with my solution?

int count=0;
for(int i=0;i<a.length();i++)
{
   for(int u=i; u<b.length(); u++)
       {
        String aSub=a.substring(i,i+1);
        String bSub=b.substring(u,u+1);
        if(aSub.equals(bSub))
        count++;
    }
}
return count;
}

Upvotes: 1

Views: 369

Answers (3)

TechnoCrat
TechnoCrat

Reputation: 708

 String a = "xxcaazz";
        String b = "xxbaaz";
        int count = 0;

        for (int i = 0; i < (a.length() > b.length() ? b : a).length() - 1; i++) {
            String aSub = a.substring(i, i + 2);
            String bSub = b.substring(i, i + 2);
            if (aSub.equals(bSub)) {
                count++;
            }
        }
        System.out.println(count);

Upvotes: 0

Rohit Jain
Rohit Jain

Reputation: 213243

In order to fix your solution, you really don't need the inner loop. Since the index should be same for the substrings in both string, only one loop is needed.

Also, you should iterate till 2nd last character of the smaller string, to avoid IndexOutOfBounds. And for substring, give i+2 as second argument instead.

Overall, you would have to change your code to something like this:

int count=0;
for(int i=0; i < small(a, b).length()-1; i++)
{
        String aSub=a.substring(i,i+2);
        String bSub=b.substring(i,i+2);
        if(aSub.equals(bSub))
        count++;
    }
}
return count;

Why I asked about the length of string is, it might become expensive to create substrings of length 2 in loop. For length n of smaller string, you would be creating 2 * n substrings.

I would rather not create substring, and just match character by character, while keeping track of whether previous character matched or not. This will work perfectly fine in your case, as length of substring to match is 2. Code would be like:

String a = "iaxxai";
String b = "aaxxaaxx";

boolean lastCharacterMatch = false;
int count = 0;

for (int i = 0; i < Math.min(a.length(), b.length()); i++) {
  if (a.charAt(i) == b.charAt(i)) {
    if (lastCharacterMatch) {
      count++;  
    } else {
      lastCharacterMatch = true;
    }
  } else {
    lastCharacterMatch = false;
  }
}

System.out.println(count);

Upvotes: 1

Foosh
Foosh

Reputation: 1197

The heart of the problem lies with your usage of the substring method. The important thing to note is that the beginning index is inclusive, and the end index is exclusive.

As an example, dissecting your usage, String aSub=a.substring(i,i+1); in the first iteration of the loop i = 0 so this line is then String aSub=a.substring(0,1); From the javadocs, and my explanation above, this would result in a substring from the first character to the first character or String aSub="x"; Changing this to i+2 and u+2 will get you the desired behavior but beware of index out of bounds errors with the way your loops are currently written.

Upvotes: 0

Related Questions