Skip to content

Instantly share code, notes, and snippets.

@vishnujayvel
Created March 18, 2015 12:04
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vishnujayvel/4dbdc815019ed00cadb4 to your computer and use it in GitHub Desktop.
Save vishnujayvel/4dbdc815019ed00cadb4 to your computer and use it in GitHub Desktop.
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,st,end) for(int i=st;i<end;i++)
#define db(x) cout << (#x) << " = " << x << endl;
#define mp make_pair
#define pb push_back
#define MAX 100005
typedef long long int ll;
int main(){
int n;
string str1,str2;
cin>>n;
cin>>str1>>str2;
//This 2D array is used to store mismatched characters from String S and String T respectively which are in the same index
//if sameIndex[0][1]=1 then it means 'a' from String S and 'b' from String T are in same index
//if sameIndex[1][0]=1 then it means 'b' from S and 'a' from T are in same index
int sameIndex[26][26]={0};
//The below array is used to store the indexes of the mismatched characters in string T
//NOTE: String S and T are represented by str1 and str2 in the code and comments from now on
int match[26];
int ham=0;
int f=0;
pair<int,int> ans;
memset(match,-1,sizeof match);
REP(i,n){
sameIndex[str1[i]-'a'][str2[i]-'a']=1;
if(str1[i]!=str2[i]){
match[str2[i]-'a']=i;
ham++;
}
}
REP(i,n){
if(str1[i]!=str2[i]){
//Case 1
//If characters str1[i] and str2[i] are different
//check if character str2[i] in string str1 and str1[i] in string str2 are present in same index
//if present then the 2 characters can be swapped and thus hamming distance will be decremented by 2
if(sameIndex[str2[i]-'a'][str1[i]-'a']){
ham-=2;
f=1;
REP(j,n){
if(str1[j]==str2[i]&&str2[j]==str1[i]){
ans.first=i+1;
ans.second=j+1;
break;
}
}
break;
}
}
}
if(!f){
REP(i,n){
//Case 2
//check if mismatched character belonging to str1 is present in mismatched character set of str2
//if present then we can swap str1[i] with the index where str1[i] is present in str2
if(str1[i]!=str2[i]){
if(match[str1[i]-'a']!=-1){
f=1;
ans.first=i+1;
ans.second=match[str1[i]-'a']+1;
ham--;
break;
}
}
}
}
cout<<ham<<endl;
if(f){
cout<<ans.first<<" "<<ans.second<<endl;
}
else{
cout<<"-1 -1";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment