fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. //#include <boost/multiprecision/cpp_int.hpp>
  4. //using namespace boost::multiprecision;
  5. #define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  6. #pragma GCC optimize "trapv"
  7. #define _GLIBCXX_DEBUG
  8. #define ll long long int
  9. #define ld long double
  10. #define ull unsigned long long int  // ranges from (0 - twice of long long int)
  11. #define rep(i,a,n) for (ll i=a;i<n;i++)
  12. #define per(i,a,n) for (ll i=n-1;i>=a;i--)
  13. #define pb push_back
  14. #define mp make_pair
  15. #define vll vector<ll>
  16. #define mod 1000000007LL
  17. #define llpair pair<ll,ll>
  18. #define INF 1000000000000000000ll
  19. #define np next_permutation
  20. #define PI acos(-1)
  21. #define deb(x) cout<<#x<<" "<<x<<endl;
  22. #define rotate_left(vec,amt) rotate(vec.begin(),vec.begin()+amt,vec.end());
  23. #define rotate_right(vec,amt) rotate(vec.begin(),vec.begin()+vec.size()-amt,vec.end());
  24. #define all(x) x.begin(),x.end()
  25. #define sortall(x) sort(all(x))
  26. #define clr(x) memset(x,0,sizeof(x))
  27.  
  28.  
  29.  
  30. int main() {
  31.   //  auto start = chrono::high_resolution_clock::now();
  32.     fio;
  33.     ll t=1; 
  34.     cin>>t;
  35.     while(t--)
  36.     {
  37. 		ll n; cin>>n;
  38. 		string s1,s2; cin>>s1>>s2;
  39. 		bool flag=true;
  40. 		for(int i=0;i<s1.length();i++)
  41. 		{
  42. 			if(s1[i]>s2[i])
  43. 			{
  44. 				flag=false;
  45. 				break;
  46. 			}
  47. 		}
  48.  
  49. 		if(flag==false)
  50. 		cout<<-1<<"\n";
  51. 		else
  52. 		{
  53. 			// ans always exists
  54. 			map<char,set<char>>mp;
  55. 			map<char,char>mp2; // for updating the value;
  56.  			for(int i=0;i<s1.length();i++)
  57. 			{
  58. 				if(s2[i]!=s1[i])
  59. 				mp[s2[i]].insert(s1[i]);
  60. 			}
  61.  
  62. 			ll ans=0;
  63.  
  64. 			for(auto x: mp)
  65. 			{
  66. 				char ch=x.first;
  67. 				set<char>st=x.second;
  68. 				for(auto y: st)
  69. 				{
  70. 					ll val=y;
  71. 					if(mp2.count(y)==1) // if updation is required
  72.  					{
  73. 						st.erase(y);
  74. 						st.insert(mp2[val]);  // add updated element
  75.  
  76.  
  77. 					}
  78.  
  79. 				}
  80.  
  81. 				// now check
  82. 				for(auto y:st)
  83. 				{
  84. 					if(y==ch)
  85. 					st.erase(y);
  86. 				}
  87.  
  88. 				// when updation and removing redudant element is done
  89. 				ans+=st.size();
  90. 				for(auto y: st)
  91. 				{
  92. 					mp2[y]=ch;  // update the value;
  93. 				}
  94.  
  95.  
  96. 			}
  97.  
  98. 			cout<<ans<<"\n";
  99.  
  100.  
  101. 		}
  102.  
  103. 	}
  104.     //auto finish = chrono::high_resolution_clock::now();
  105.  //   cerr << "Time elapsed: " << (chrono::duration<long double>(finish-start)).count() << "s\n";
  106.     return 0;
  107.  
  108. }
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
Success #stdin #stdout 0s 4336KB
comments (?)
stdin
copy 
5
3
aab
bcc
4
cabc
abcb
3
abc
tsr
4
aabd
cccd
5
abcbd
bcdda
stdout
copy 
2
-1
3
2
-1
https://ideone.com/1rkrfL
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!