Analyzing the mistakes people make while typing search queries is a complex and an interesting work. As there is no guaranteed way to determine what the user originally meant by typing some query, we have to use different sorts of heuristics.
Polycarp needed to write a code that could, given two words, check whether they could have been obtained from the same word as a result of typos. Polycarpus suggested that the most common typo is skipping exactly one letter as you type a word.
Implement a program that can, given two distinct words S and T of the same length n determine how many words W of length n + 1 are there with such property that you can transform W into both S, and T by deleting exactly one character. Words S and T consist of lowercase English letters. Word W also should consist of lowercase English letters.
Input
The first line contains integer n (1 ≤ n ≤ 100 000) — the length of words S and T.
The second line contains word S.
The third line contains word T.
Words S and T consist of lowercase English letters. It is guaranteed that S and T are distinct words.
Output
Print a single integer — the number of distinct words W that can be transformed to S and T due to a typo.
Examples
input
7
reading
trading
output
1
input
5
sweet
sheep
output
0
input
3
toy
try
output
2
Note
In the first sample test the two given words could be obtained only from word ” treading” (the deleted letters are marked in bold).
In the second sample test the two given words couldn’t be obtained from the same word by removing one letter.
In the third sample test the two given words could be obtained from either word “tory” or word “troy”.
Solution:
import java.io.Reader;
import java.util.InputMismatchException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.IOException;
/**
* Built using CHelper plug-in
* Actual solution is at the top
* @author Niyaz Nigmatullin
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
FastScanner in = new FastScanner(inputStream);
FastPrinter out = new FastPrinter(outputStream);
TaskE solver = new TaskE();
solver.solve(1, in, out);
out.close();
}
}
class TaskE {
static boolean check(String t, String s) {
int cur = 0;
for (int i = 0; i < t.length(); i++) {
if (cur < s.length() && t.charAt(i) == s.charAt(cur)) {
++cur;
}
}
return cur == s.length();
}
public void solve(int testNumber, FastScanner in, FastPrinter out) {
in.next();
String s = in.next();
String t = in.next();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != t.charAt(i)) {
int ans = 0;
{
String f = s.substring(0, i) + t.charAt(i) + s.substring(i);
if (check(f, s) && check(f, t)) ++ans;
}
{
String f = t.substring(0, i) + s.charAt(i) + t.substring(i);
if (check(f, s) && check(f, t)) ++ans;
}
out.println(ans);
return;
}
}
}
}
class FastScanner extends BufferedReader {
public FastScanner(InputStream is) {
super(new InputStreamReader(is));
}
public int read() {
try {
int ret = super.read();
// if (isEOF && ret < 0) {
// throw new InputMismatchException();
// }
// isEOF = ret == -1;
return ret;
} catch (IOException e) {
throw new InputMismatchException();
}
}
public String next() {
StringBuilder sb = new StringBuilder();
int c = read();
while (isWhiteSpace(c)) {
c = read();
}
if (c < 0) {
return null;
}
while (c >= 0 && !isWhiteSpace(c)) {
sb.appendCodePoint(c);
c = read();
}
return sb.toString();
}
static boolean isWhiteSpace(int c) {
return c >= 0 && c <= 32;
}
public String readLine() {
try {
return super.readLine();
} catch (IOException e) {
return null;
}
}
}
class FastPrinter extends PrintWriter {
public FastPrinter(OutputStream out) {
super(out);
}
}
