# Check if String Follows Order of Characters by a Pattern or not

Difficulty Level Medium
Pattern Searching StringViews 1472

## Problem Statement

In the “Check if String Follows Order of Characters by a Pattern or not” problem we have to check if characters in the given input string follow the same order as determined by characters present in the given input pattern then print “Yes” else print “No”.

## Input Format

The first line containing a string s.

The second line containing a pattern string.

## Output Format

Print “Yes” if the input string follows the same order as determined by characters present in the given input pattern. Otherwise, print “No”.

## Constraints

• 1<=|s|<=10^6
• s[i] is any lowercase and uppercase alphabet character.
• 1<=|pattern_string|<=52
• pattern_string[i] is any lowercase and uppercase alphabet character.

## Example

```programming
ra```
`True`

Explanation: In the given input string “programming” all r`s are before a. So, the input string follows the same order as in the pattern string. That’s why our ans is “Yes”.

```programming
gra```
`False`

Explanation: There are 2 r`s and a before g in the input string. So, the input string does not follow the same order as in the pattern string. That’s why our ans is “No”.

## Algorithm

1. Assign labels(numbers) to the characters of the pattern word.

2. Keep track of order of last visited character.

3. If label of current character is less than previous character, return false.

4. Else, update last label.

5. If it reaches the end it means all characters follow order, return true.

## Implementation to Check if String Follows Order of Characters by a Pattern or not

### C++ Program

```#include <bits/stdc++.h>
using namespace std;

bool checkPattern(string str, string pat)
{
vector<int> label(260, -1);
int order = 1;
for (int i = 0; i < pat.length() ; i++)
{
label[pat[i]] = order;
order++;
}
int last_order = -1;
for (int i = 0; i < str.length(); i++)
{
if (label[str[i]] != -1)
{
if(label[str[i]]<last_order)
return false;
last_order =  label[str[i]];
}
}
return true;
}

int main()
{
string s,t;
cin>>s>>t;
if(checkPattern(s,t))
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
return 0;
}```

### Java Program

```import java.util.Scanner;

class sum {

public static int checkPattern(String str, String pat)
{
int[] label = new int;
for(int i=0;i<260;i++)
{
label[i] = -1;
}
int order = 1;
for(int i=0;i<pat.length();i++)
{
label[pat.charAt(i)] = order;
order++;
}
int last_order = -1;
for (int i = 0; i < str.length(); i++)
{
if(label[str.charAt(i)] != -1)
{
if (label[str.charAt(i)] < last_order)
return 0;
last_order = label[str.charAt(i)];
}
}
return 1;
}
public static void main(String[] args)
{
Scanner sr= new Scanner(System.in);
String s = sr.next();
String t = sr.next();
if(checkPattern(s,t)==1)
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}```
```programming
ra```
`Yes`

## Complexity Analysis

### Time Complexity

O(n) where n is the size of the given string “s”. Here we traverse the string t and check for the order of the character in constant time.

### Space Complexity

O(1) because here we use only space of integer array or vector of size 260 which is nearest to constant if n is big like 10^6.

Translate »