# Check if a pair of strings exists that starts with and without the character K or not

Given an array **arr[]** consisting of **N** strings of lowercase characters and a character **K** such that any string may start with the character **K**, the task is to check if there exists any pair of strings that are starting and not starting (‘!’) with the character **K**. If found to be **true**, then print “**Yes**“. Otherwise, print “**No**“.

**Examples:**

Input:arr[] = {“a”, “!a”, “b”, “!c”, “d”, “!d”}, K = ‘!’Output:YesExplanation:

There exists valid pairs of the strings are {(“a”, “!a”), (“!d”, “d”)}.

Input:arr[] = {“red”, “red”, “red”, “!orange”, “yellow”, “!blue”, “cyan”, “!green”, “brown”, “!gray”}, K = ‘!’Output:No

**Naive Approach:** The simplest approach to solve the given problem is to find all possible pairs from the array and check if the strings pair satisfy the given condition or not.

**Time Complexity:** O(N^{2}*M), where M is the maximum *length of the string** in the given array arr[].*

**Auxiliary Space:**O(1)**Efficient Approach:** The above approach can also be solved by using dictionary. Follow the steps below to solve the problem:

- Initialize a dictionary, say,
**visited**to store the previously visited strings. - Iterate over the list
**arr[]**and in each iteration, if the starting character of the current string is the character**K**then check for string without the character**K**in**visited**otherwise, check for the string with the character**K**in**visited**. If the string is found then return “**Yes**“. - In each iteration, add the string
**S**into the map**visited**. - After completing the above steps, print “
**No**” if the above conditions are not satisfied.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to check whether a pair of` `// strings exists satisfying the conditions` `string checkhappy(vector<string> arr, ` `char` `K, ` `int` `N)` `{` ` ` ` ` `// Stores the visited strings` ` ` `set<string> visited;` ` ` `// Iterate over the array arr[]` ` ` `for` `(string s : arr) {` ` ` `// If first character of current` ` ` `// string is K` ` ` `if` `(s[0] == K)` ` ` `if` `(visited.find(s.substr(1)) != visited.end())` ` ` `return` `"Yes"` `;` ` ` ` ` `// Otherwise` ` ` `else` ` ` `if` `(visited.find((K + s)) != visited.end())` ` ` `return` `"Yes"` `;` ` ` ` ` `// Adding to the visited` ` ` `visited.insert(s);` ` ` `}` ` ` `return` `"No"` `;` `}` `// Driver Code` `int` `main() {` ` ` `// Given Input` ` ` `vector<string> arr = {` `"a"` `, ` `"! a"` `, ` `"b"` `, ` `"! c"` `, ` `"d"` `, ` `"! d"` `};` ` ` `char` `K = ` `'!'` `;` ` ` `int` `N = arr.size();` ` ` ` ` `cout << checkhappy(arr, K, N) << endl;` ` ` ` ` `return` `0;` `}` `// This code is contributed Dharanendra L V.` |

## Python3

`# Python program for the above approach` `# Function to check whether a pair of` `# strings exists satisfying the conditions` `def` `checkhappy(arr, K, N):` ` ` ` ` `# Stores the visited strings` ` ` `visited ` `=` `set` `()` ` ` `# Iterate over the array arr[]` ` ` `for` `s ` `in` `arr:` ` ` `# If first character of current` ` ` `# string is K` ` ` `if` `(s[` `0` `] ` `=` `=` `K):` ` ` `if` `s[` `1` `:] ` `in` `visited:` ` ` `return` `'Yes'` ` ` ` ` `# Otherwise` ` ` `else` `:` ` ` `if` `(K ` `+` `s) ` `in` `visited:` ` ` `return` `'Yes'` ` ` ` ` `# Adding to the visited` ` ` `visited.add(s)` ` ` `return` `"No"` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `# Given Input` ` ` `arr ` `=` `[` `'a'` `, ` `'! a'` `, ` `'b'` `, ` `'! c'` `, ` `'d'` `, ` `'! d'` `]` ` ` `K ` `=` `'!'` ` ` `N ` `=` `len` `(arr)` ` ` ` ` `print` `(checkhappy(arr, K, N))` |

## Javascript

`<script>` `// Javascript program for the above approach` `// Function to check whether a pair of` `// strings exists satisfying the conditions` `function` `checkhappy(arr, K, N)` `{` ` ` ` ` `// Stores the visited strings` ` ` `let visited = ` `new` `Set();` ` ` ` ` `// Iterate over the array arr[]` ` ` `for` `(let s of arr)` ` ` `{` ` ` ` ` `// If first character of current` ` ` `// string is K` ` ` `if` `(s[0] == K)` ` ` `{` ` ` `if` `(visited.has(s.slice(1)))` ` ` `return` `"Yes"` `;` ` ` `}` ` ` ` ` `// Otherwise` ` ` `else` ` ` `{` ` ` `if` `(visited.has(K + s))` ` ` `return` `"Yes"` `;` ` ` `}` ` ` ` ` `// Adding to the visited` ` ` `visited.add(s);` ` ` `}` ` ` `return` `"No"` `;` `}` `// Driver Code` `// Given Input` `let arr = [ ` `"a"` `, ` `"! a"` `, ` `"b"` `, ` `"! c"` `,` ` ` `"d"` `, ` `"! d"` `];` `let K = ` `"!"` `;` `let N = arr.length;` `document.write(checkhappy(arr, K, N));` `// This code is contributed by gfgking` `</script>` |

**Output:**

No

**Time Complexity:** O(N)**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.