A - Twice Subsequence
Source: atcoder
Difficulty: 400

Problem Statement
There is a sequence
A = (A_1,\dots,A_N)
. Determine whether there are at least two subsequences of
A
that match the sequence
B = (B_1,\dots,B_M)
. Two subsequences are distinguished if they are taken from different positions, even if they coincide as sequences.
Subsequence
A subsequence of
A
is a sequence obtained by removing zero or more elements from
A
and leaving the remaining elements in their original order.
Constraints
1 \leq M \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^9
1 \leq B_i \leq 10^9
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
M
A_1
A_2
\ldots
A_N
B_1
B_2
\ldots
B_M
Output
If there are at least two subsequences of
A
that match
B
, print
Yes
. Otherwise, print
No
.
Sample Input 1
4 2
1 2 1 2
1 2
Sample Output 1
Yes
There are three subsequences of
A
that match
B
:
(A_1,A_2), (A_1,A_4), (A_3,A_4)
.
Sample Input 2
3 2
1 2 1
1 2
Sample Output 2
No
There is only one subsequence of
A
that matches
B
:
(A_1,A_2)
.
Sample Input 3
3 2
1 1 2
2 1
Sample Output 3
No
There are no subsequences of
A
that match
B
.

C++ solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(x,l,r) for(int x=l;x<=r;x++)
#define per(x,r,l) for(int x=r;x>=l;x--)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()

const int MOD=998244353,INF=1e9;
const ll LNF=1e18;
int power(int a,int k,int mod=MOD) {
    a%=mod,k%=mod-1; if(k<0) k+=mod-1;
    int res=1; while(k) {
        if(k&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod; k>>=1;
    } return res;
}
void add(int &x,int y) {x=(x+y>=MOD?x+y-MOD:x+y);}
void sub(int &x,int y) {x=(x>=y?x-y:x-y+MOD);}
int gcd(int x,int y) {return y?gcd(y,x%y):x;}
void chkmax(int &x,int y) {x<y?x=y:0;}
void chkmin(int &x,int y) {x>y?x=y:0;}

const int N=200200;

int n,m;
int a[N],b[N];

int x[N],y[N];

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    rep(i,1,n) cin>>a[i];
    rep(i,1,m) cin>>b[i];
    int p=0;
    rep(i,1,n) {
        if(p<m&&a[i]==b[p+1]) {
            p++;
            x[p]=i;
        }
    }
    if(p!=m) {
        cout<<"No\n";
        return 0;
    }
    p=m;
    per(i,n,1) {
        if(p>=1&&a[i]==b[p]) {
            y[p]=i;
            p--;
        }
    }
    int fl=0;
    rep(i,1,m) if(x[i]!=y[i]) fl=1;
    if(fl) cout<<"Yes\n"; else cout<<"No\n";
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextInts(n int) []int {
	res := make([]int, n)
	for i := range res {
		res[i] = nextInt()
	}
	return res
}

func main() {
	sc.Split(bufio.ScanWords)
	defer wr.Flush()

	n := nextInt()
	m := nextInt()
	a := nextInts(n)
	b := nextInts(m)

	fwdIndices := make([]int, m)
	bIdx := 0
	for aIdx := 0; aIdx < n && bIdx < m; aIdx++ {
		if a[aIdx] == b[bIdx] {
			fwdIndices[bIdx] = aIdx
			bIdx++
		}
	}

	if bIdx != m {
		fmt.Fprintln(wr, "No")
		return
	}

	bwdIndices := make([]int, m)
	bIdx = m - 1
	for aIdx := n - 1; aIdx >= 0 && bIdx >= 0; aIdx-- {
		if a[aIdx] == b[bIdx] {
			bwdIndices[bIdx] = aIdx
			bIdx--
		}
	}
    
    foundTwo := false
    for k := 0; k < m; k++ {
		if fwdIndices[k] < bwdIndices[k] {
            foundTwo = true
			break
		}
	}

	if foundTwo {
		fmt.Fprintln(wr, "Yes")
	} else {
		fmt.Fprintln(wr, "No")
	}
}

Java solution:
import java.util.*;
import java.io.*;

import java.util.Objects;
import java.util.stream.Collectors;

import static java.lang.Math.*;
import static java.lang.System.out;

public class Main {

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
    public static int[] dp;
    public static long mod = (long)998244353;
    public static char[] a, b, c;
    public static int[] x;
    public static boolean[] visited;
    public static HashMap<Integer, HashSet<Integer>> map;
    public static ArrayList<ArrayList<Integer>> adj;
    public static void main(String[] args) {

        FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        int test = 1;
        while (test-- > 0) {
            int n = in.nextInt();
            int m = in.nextInt();
            int[] a = new int[n];
            int[] b = new int[m];
            for( int i = 0; i < n ; i++ ) a[i] = in.nextInt();
            for( int i = 0; i < m ; i++ ) b[i] = in.nextInt();
            // there is atleast 2 subsequences of A that match B
            int j = 0; int i = 0;
            HashSet<Integer> sub1 = new HashSet<>();
            for( i = 0; i < n && j < m ; ) {
                if( a[i] == b[j] ) {
                    sub1.add(i);
                    i++;
                    j++;
                } else i++;
            }
            if( j != m ) out.println("No");
            else {
                // abccc
                // abc
                i = n-1; j = m-1;
                HashSet<Integer> sub2 = new HashSet<>();

                for( ; j >= 0 && i >= 0 ; ) {
                    if( a[i] == b[j]) {
                        sub2.add(i);
                        i--;
                        j--;
                    } else i--;
                }
//                out.println(sub1);
//                out.println(sub2);
                if( j != -1 || sub1.containsAll(sub2)) out.println("No");
                else out.println("Yes");
            }
        }
        out.flush();
        out.close();
    }
    //  1 2 3 1 2
    // 1 2 3
    public static int dfs( int i, HashSet<Integer> reacheable ) {
//        if( x[i] != -1 ) return x[i];
        if( reacheable.contains(i)) return 0;
        else if( visited[i]) {
            reacheable.add(i);
            reacheable.addAll(map.get(i));
            return x[i];
        }
//        visited[i] = true;
        int sum = 1;
        reacheable.add(i);
        for( int next : adj.get(i)) {
            sum += dfs(next, reacheable);
        }
        return sum;
    }
    public static void fillGrid( int minX, int maxX, int minY, int maxY, char[][] ch ) {
        if( minX == maxX ) return;
        int lenX = maxX-minX+1;
        int lenY = maxY-minY+1;
        int minCX = minX + (lenX/3);
        int maxCX = maxX - (lenX/3);
        int minCY = minY + (lenY/3);
        int maxCY = maxY - (lenY/3);
        for( int i = minCX; i <= maxCX; i++ ) {
            for( int j = minCY; j <= maxCY; j++ ) {
                ch[i][j]= '.';
            }
        }
        fillGrid(minX, minCX-1, minY, minCY-1, ch);
        fillGrid(minX, minCX-1, minCY, maxCY, ch);
        fillGrid(minX, minCX-1, maxCY+1, maxY, ch);

        fillGrid(minCX, maxCX, minY, minCY-1, ch);
//        fillGrid(minCX, maxCX, minCY, maxCY, ch);
        fillGrid(minCX, maxCX, maxCY+1, maxY, ch);

        fillGrid(maxCX+1, maxX, minY, minCY-1, ch);
        fillGrid(maxCX+1, maxX, minCY, maxCY, ch);
        fillGrid(maxCX+1, maxX, maxCY+1, maxY, ch);
    }
    public static int findMinDeletions( int x, int d, int max, HashMap<Integer, Integer> freq ) {
        if(x > max) return 0;
        if( dp[x] != -1 ) return dp[x];
        // have x
        if( freq.containsKey(x)) return dp[x] = Math.max(freq.get(x)+findMinDeletions(x+2*d, d, max, freq), findMinDeletions(x+d, d, max, freq));
        else return dp[x] = findMinDeletions(x+d, d, max, freq);
    }
    public static boolean getMFlowers( int[] a, int[] b, int idx ) {
        int m = b.length; int n = a.length;
        int i, j;
        for( i = 0, j = 0; j < m && i < n ; i++ ) {
            if( a[i] >= b[j] || ( j == idx ) ) {
                if( j == idx ) {
                    i--;
                }
                j++;
            }
        }
        if( j == idx ) j++;
        return j == m;
    }
    public static void sortArray(int[] arr) {
        List<Integer> list = Arrays.stream(arr)
                .boxed()
                .collect(Collectors.toList());

        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }

    public static void reverse(int[] a ) {
        int n = a.length;
        for( int i = 0; i < a.length/2; i++ ) {
            int temp = a[i];
            a[i] = a[n-1-i];
            a[n-i-1] = temp;
        }
    }

    public static void computeSPF( int[] spf, boolean[] primes ) {
        for( int i = 2; i <= (int)1e7; i++ ) spf[i] = 2;

        for( int i = 3; i < (int)1e7; i+=2 ) {
            if( primes[i] ) {
                spf[i] = i;
                for( long j = (long)i; j*i < (long)1e7; j += 2) {
                    if( primes[ (int)(i*j)]) {
                        primes[(int)(i*j)] = false;
                        spf[(int)(i*j) ] = i;
                    }
                }
            }
        }
    }
    public static boolean isPrime( int n ) {
        boolean prime = true;
        for( int i = 2; i * i <= n ; i++ ) {
            if( n % i == 0 ) prime = false;
        }
        return prime;

    }
    public static long gcd( long a, long b ) {
        if( b == 0 ) return a;
        return gcd(b, a % b );
    }
    public static long nCr( int n, int r ) {
        if( r > n ) return 0;
        // nCr = n!/r!*(n-r)
        long x = 1;
        for( int i = n-r+1; i <= n ; i++ ) x *= i;
        for(int i = 2; i <= r; i++ ) x /= i;
        return x;
    }
    static final int MOD = (int)(Math.pow(10, 9))+7;
    static long[] fac = new long[300001];

    static long power(long x, long y, long p) {
        long res = 1;
        x %= p;

        while (y > 0) {
            if ((y & 1) != 0)
                res = (res * x) % p;
            y >>= 1;
            x = (x * x) % p;
        }
        return res;
    }

    static long modInverse(long n, long p) {
        return power(n, p - 2, p);
    }

    static long nCr(int n, int r, long p) {
        if (n < r)
            return 0;

        if (r == 0)
            return 1;

        return fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p;
    }

    static void computeFactorials() {
        fac[0] = 1;
        for (int i = 1; i < fac.length; i++)
            fac[i] = fac[i - 1] * i % MOD;
    }
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = 1;
  while(q--)print(solve()?"Yes":"No");
}

function solve(){
  var [n,m] = nexts(2);
  var a = nexts(n);
  var b = nexts(m);
  var c = [], x = 0;
  for(var i = 0; i < n && x < m; i++){
    if(a[i] === b[x])c.push(i), x++;
  }
  if(x < m)return 0;
  x = m-1;
  for(var i = n-1; i >= 0 && x >= 0; i--){
    if(a[i] === b[x]){
      if(c.at(-1) !== i)return 1;
      c.pop();
      x--;
    }
  }
  return 0;
}

Python solution:
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
j = 0
f = False
for i in range(n):
  if j < m and a[i] == b[j]:
    j += 1
  elif j > 0 and a[i] == b[j - 1]:
    f = True
if f and j == m:
  print("Yes")
else:
  print("No")

Ruby solution:
n,m=gets.split.map(&:to_i)
a=gets.split.map(&:to_i)
b=gets.split.map(&:to_i)

a1=[]
j=0
f=false
n.times do |i|
  if a[i]==b[j]
    a1 << i
    j+=1
  end
  if j==m
    f=true
    break
  end
end
if !f
  puts "No"
  exit
end

j=m-1
a2=[]
(n-1).downto(0) do |i|
  if a[i]==b[j]
    a2 << i
    j-=1
  end
  if j==-1
    f=true
    break
  end
end
if !f
  puts "No"
  exit
end

if a1==a2.reverse
  puts "No"
else
  puts "Yes"
end