Crazy scientist

Title Description
Farmer John Our distant relatives Ben Is a crazy scientist .

Usually this will cause a lot of friction at family gatherings , But this occasionally brings some benefits , Especially when Farmer John When he found that he was facing some unique and unusual problems about his cows .

Farmer John Currently facing a unique and unusual question about her cows .

He recently ordered N A cow , Contains two different varieties ： Holstein and gensai cattle .

He used a long in the order N String to specify , The characters are H（ Holstein cattle ） or G（ It means more cattle racing ）.

Unfortunately , When these cows arrive at his farm , When he lined them up , The string of their varieties is different from the original .

We call these two strings A and B, among A yes Farmer John A string consisting of characters of the original desired variety ,B It's a string of his cows when they arrive .

Farmer John There is no simple check for rearrangement B Whether the cows in the can get A, Instead, he invited his distant relatives Ben Use his scientific talent to solve this problem .

After months of research ,Ben Invented an unusual machine ： Cow variety conversion machine 3000, Be able to select a substring of any cow and reverse their breed ： All in this substring H Turn into G, all G Turn into H.

Farmer John Want to ask for his current sequence B Into what he wanted when he ordered A The minimum number of times you need to use this machine .

However ,Ben Crazy scientist skills don't deal with anything other than developing strange machines , So you need help Farmer John Solve this computational problem .

Input format
The first line of input contains N, The following two lines contain the string A and B. Each string contains N Characters , All characters are H and G One of .

Output format
The output will B Turn into A The minimum number of times the machine needs to be used .

Data range
1≤N≤1000

 Examples 
 sample input ：
7
GHHHGHH
HHGGGHH
 sample output ：
2
 Sample explanation 
 First ,FJ  You can change only the substring composed of the first character , take  B  Turn into  GHGGGHH.

 then , He can change the substring composed of the third and fourth characters , obtain  A.

 Of course , There are other effective schemes to perform two operations .

Double pointer Actual operation is less than O(n2)O(n2)
Double pointer template ：

for(int i=0,j=0;i<n;i++)
{
    while(j<i && check(i,j)) j++;
    // The specific logic of each topic
}

Simple solution ：

for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)

The core of optimization is i and j The law of change —— monotonicity ;
In this question, as long as one character of the two strings is different , You need to continue to judge the following characters
Until one character of the two strings is the same, it means that the machine works successfully this time ;
If the characters of the two strings are the same at this time, it means that the machine does not work
We will find that j be relative to i It must be moving forward , Therefore, we can adopt the double pointer Algorithm
What is required in this question is the number of times the machine works ans

Time complexity   Less than O(n^2)
reference
C++ Code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n,ans;
string s1,s2;
int main()
{
    cin>>n>>s1>>s2;
    for (int i = 0; i < n; i ++ )
    {
        if(s1[i]!=s2[i])
        {
            ans++;
            int j=i+1;
            while(j<n&&s1[j]!=s2[j])j++;
            i=j-1;
        }
    }
    return cout<<ans,0;
}

Java Code

import java.io.*;
import java.util.*;
public class Main {
    static int ans;
    public static void main(String args[])  {
      Scanner cin = new Scanner(System.in); 
       int n=cin.nextInt();
       String s1=cin.next(),s2=cin.next();
       for (int i = 0; i < n; i ++ )
       {
        if(s1.charAt(i)!=s2.charAt(i))
        {
            ans++;
            int j=i+1;
            while(j<n&&s1.charAt(j)!=s2.charAt(j))j++;
            i=j-1;
        }
       }
       System.out.println(ans);
       return ;
    }
}

Welcome to leave a message like

Ouch, ouch