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

Difficulty Level Medium
Frequently asked in Adobe Amazon GreyOrange InfoEdge Microsoft
Pattern Searching StringViews 2531

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[260];  
        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 »