Given an array of strings str[] of length N, consisting of strings of the same length, the task is to find the string which only differs by a single character from all the given strings. If no such string can be generated, print -1. In case of multiple possible answers, print any of them.
Example:
Input: str[] = { “abac”, “zdac”, “bdac”}
Output: adac
Explanation:
The string “adac” differs from all the given strings by a single character.Input: str[] = { “neveropen”, “teeds”}
Output: teeks
Approach: Follow the steps below to solve the problem:
- Set the first string as the answer.
- Now, replace the first character of the string to all possible characters and check if it differs by a single character from the other strings or not.
- Repeat this process for all the characters in the first string.
- If any such string of the required type is found from the above step, print the string.
- If no such situation arises where replacing a single character of the first string generates a string of the required type, print -1.
Below is the implementation of the above approach.
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>#define ll long longusing namespace std;// Function to check if a given string// differs by a single character from// all the strings in an arraybool check(string ans, vector<string>& s, int n, int m){ // Traverse over the strings for (int i = 1; i < n; ++i) { // Stores the count of characters // differing from the strings int count = 0; for (int j = 0; j < m; ++j) { if (ans[j] != s[i][j]) count++; } // If differs by more than one // character if (count > 1) return false; } return true;}// Function to find the string which only// differ at one position from the all// given strings of the arraystring findString(vector<string>& s){ // Size of the array int n = s.size(); // Length of a string int m = s[0].size(); string ans = s[0]; int flag = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < 26; ++j) { string x = ans; // Replace i-th character by all // possible characters x[i] = (j + 'a'); // Check if it differs by a // single character from all // other strings if (check(x, s, n, m)) { ans = x; flag = 1; break; } } // If desired string is obtained if (flag == 1) break; } // Print the answer if (flag == 0) return "-1"; else return ans;}// Driver codeint main(){ vector<string> s = { "neveropen", "teeds" }; // Function call cout << findString(s) << endl;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ // Function to check if a given string// differs by a single character from// all the strings in an arraystatic boolean check(String ans, String[] s, int n, int m){ // Traverse over the strings for(int i = 1; i < n; ++i) { // Stores the count of characters // differing from the strings int count = 0; for(int j = 0; j < m; ++j) { if (ans.charAt(j) != s[i].charAt(j)) count++; } // If differs by more than one // character if (count > 1) return false; } return true;}// Function to find the string which only// differ at one position from the all// given strings of the arraystatic String findString(String[] s){ // Size of the array int n = s.length; String ans = s[0]; // Length of a string int m = ans.length(); int flag = 0; for(int i = 0; i < m; ++i) { for(int j = 0; j < 26; ++j) { String x = ans; // Replace i-th character by all // possible characters x = x.replace(x.charAt(i), (char)(j + 'a')); // Check if it differs by a // single character from all // other strings if (check(x, s, n, m)) { ans = x; flag = 1; break; } } // If desired string is obtained if (flag == 1) break; } // Print the answer if (flag == 0) return "-1"; else return ans;}// Driver codepublic static void main(String []args){ String s[] = { "neveropen", "teeds" }; // Function call System.out.println(findString(s));}}// This code is contributed by chitranayal |
Python3
# Python3 program to implement# the above approach# Function to check if a given string # differs by a single character from# all the strings in an arraydef check(ans, s, n, m): # Traverse over the strings for i in range(1, n): # Stores the count of characters # differing from the strings count = 0 for j in range(m): if(ans[j] != s[i][j]): count += 1 # If differs by more than one # character if(count > 1): return False return True# Function to find the string which only# differ at one position from the all# given strings of the arraydef findString(s): # Size of the array n = len(s) # Length of a string m = len(s[0]) ans = s[0] flag = 0 for i in range(m): for j in range(26): x = list(ans) # Replace i-th character by all # possible characters x[i] = chr(j + ord('a')) # Check if it differs by a # single character from all # other strings if(check(x, s, n, m)): ans = x flag = 1 break # If desired string is obtained if(flag == 1): break # Print the answer if(flag == 0): return "-1" else: return ''.join(ans)# Driver Code# Given array of stringss = [ "neveropen", "teeds" ]# Function callprint(findString(s))# This code is contributed by Shivam Singh |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to check if a given string// differs by a single character from// all the strings in an arraystatic bool check(String ans, String[] s, int n, int m){ // Traverse over the strings for(int i = 1; i < n; ++i) { // Stores the count of characters // differing from the strings int count = 0; for(int j = 0; j < m; ++j) { if (ans[j] != s[i][j]) count++; } // If differs by more than one // character if (count > 1) return false; } return true;}// Function to find the string which only// differ at one position from the all// given strings of the arraystatic String findString(String[] s){ // Size of the array int n = s.Length; String ans = s[0]; // Length of a string int m = ans.Length; int flag = 0; for(int i = 0; i < m; ++i) { for(int j = 0; j < 26; ++j) { String x = ans; // Replace i-th character by all // possible characters x = x.Replace(x[i], (char)(j + 'a')); // Check if it differs by a // single character from all // other strings if (check(x, s, n, m)) { ans = x; flag = 1; break; } } // If desired string is obtained if (flag == 1) break; } // Print the answer if (flag == 0) return "-1"; else return ans;}// Driver codepublic static void Main(String []args){ String []s = { "neveropen", "teeds" }; // Function call Console.WriteLine(findString(s));}}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to implement // the above approach // Function to check if a given string // differs by a single character from // all the strings in an array function check(ans, s, n, m) { // Traverse over the strings for (var i = 1; i < n; ++i) { // Stores the count of characters // differing from the strings var count = 0; for (var j = 0; j < m; ++j) { if (ans[j] !== s[i][j]) count++; } // If differs by more than one // character if (count > 1) return false; } return true; } // Function to find the string which only // differ at one position from the all // given strings of the array function findString(s) { // Size of the array var n = s.length; var ans = s[0]; // Length of a string var m = ans.length; var flag = 0; for (var i = 0; i < m; ++i) { for (var j = 0; j < 26; ++j) { var x = ans; // Replace i-th character by all // possible characters x = x.replace(x[i], String.fromCharCode(j + "a".charCodeAt(0))); // Check if it differs by a // single character from all // other strings if (check(x, s, n, m)) { ans = x; flag = 1; break; } } // If desired string is obtained if (flag === 1) break; } // Print the answer if (flag === 0) return "-1"; else return ans; } // Driver code var s = ["neveropen", "teeds"]; // Function call document.write(findString(s)); // This code is contributed by rdtank. </script> |
Output
teeks
Time Complexity: O(N * M2 * 26)
Auxiliary Space: O(M)
Another approach: using a hash table
We can iterate over each string in the given array and for each character in the string, we can replace it with all the possible characters and store the resulting strings in the hash table along with their frequency. If a string occurs n-1 times in the hash table, where n is the number of strings in the array, then it is the required string. If no such string is found, then we can return -1.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>#define ll long longusing namespace std;// Function to find the string which only differ at one position from the all given strings of the arraystring findString(vector<string>& s){ // Size of the array int n = s.size(); // Length of a string int m = s[0].size(); // Create an unordered map to store the frequency of each generated string unordered_map<string, int> mp; // Generate all possible strings that can be formed by changing exactly one character in each input string for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { string temp = s[i]; for (char ch = 'a'; ch <= 'z'; ++ch) { temp[j] = ch; mp[temp]++; } } } // Traverse over the map and find the string that differs from all input strings at exactly one position for (auto it : mp) { if (it.second == n && s[0] != it.first) { int count = 0; for (int i = 0; i < m; ++i) { if (s[0][i] != it.first[i]) count++; } if (count == 1) return it.first; } } // If no such string is found, return "-1" return "-1";}// Driver codeint main(){ // Input vector of strings vector<string> s = {"abac", "zdac", "bdac"}; // Function call cout << findString(s) << endl; return 0;} |
Java
import java.util.HashMap;import java.util.Map;import java.util.ArrayList;import java.util.List;public class Main { // Function to find the string which only differs at one position from all given strings in the array public static String findString(List<String> s) { // Size of the array int n = s.size(); // Length of a string int m = s.get(0).length(); // Create a HashMap to store the frequency of each generated string Map<String, Integer> mp = new HashMap<>(); // Generate all possible strings that can be formed by changing exactly one character in each input string for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { String temp = s.get(i); for (char ch = 'a'; ch <= 'z'; ++ch) { char[] tempArray = temp.toCharArray(); tempArray[j] = ch; temp = new String(tempArray); mp.put(temp, mp.getOrDefault(temp, 0) + 1); } } } // Traverse the map and find the string that differs from all input strings at exactly one position for (Map.Entry<String, Integer> entry : mp.entrySet()) { String key = entry.getKey(); int value = entry.getValue(); if (value == n && !s.get(0).equals(key)) { int count = 0; for (int i = 0; i < m; ++i) { if (s.get(0).charAt(i) != key.charAt(i)) count++; } if (count == 1) return key; } } // If no such string is found, return "-1" return "-1"; } // Driver code public static void main(String[] args) { // Input list of strings List<String> s = new ArrayList<>(); s.add("abac"); s.add("zdac"); s.add("bdac"); // Function call System.out.println(findString(s)); }}// This code is contributed by rambabuguphka |
Python3
# Function to find the string which only differs at one position from all given strings in the arraydef find_string(strings): # Number of strings in the input array n = len(strings) # Length of a string (assuming all strings have the same length) m = len(strings[0]) # Create a dictionary to store the frequency of each generated string mp = {} # Generate all possible strings that can be formed by changing exactly one character in each input string for i in range(n): for j in range(m): temp = list(strings[i]) for ch in range(ord('a'), ord('z')+1): temp[j] = chr(ch) modified_string = ''.join(temp) if modified_string in mp: mp[modified_string] += 1 else: mp[modified_string] = 1 # Traverse the dictionary and find the string that differs from all input strings at exactly one position for key, value in mp.items(): if value == n and strings[0] != key: count = 0 for i in range(m): if strings[0][i] != key[i]: count += 1 if count == 1: return key # If no such string is found, return "-1" return "-1"# Driver codeif __name__ == "__main__": # Input list of strings strings = ["abac", "zdac", "bdac"] # Function call result = find_string(strings) print(result) |
C#
using System;using System.Collections.Generic;class Program { // Function to find the string which differs at one // position from all given strings static string FindString(List<string> s) { // Size of the array int n = s.Count; // Length of a string int m = s[0].Length; // Create a dictionary to store the frequency of // each generated string Dictionary<string, int> frequencyMap = new Dictionary<string, int>(); // Generate all possible strings that can be formed // by changing exactly one character in each input // string for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { char[] temp = s[i].ToCharArray(); for (char ch = 'a'; ch <= 'z'; ch++) { temp[j] = ch; string modifiedString = new string(temp); if (frequencyMap.ContainsKey( modifiedString)) { frequencyMap[modifiedString]++; } else { frequencyMap[modifiedString] = 1; } } } } // Traverse the dictionary and find the string that // differs from all input strings at exactly one // position foreach(var kvp in frequencyMap) { if (kvp.Value == n && !s[0].Equals(kvp.Key)) { int count = 0; for (int i = 0; i < m; i++) { if (s[0][i] != kvp.Key[i]) { count++; } } if (count == 1) { return kvp.Key; } } } // If no such string is found, return "-1" return "-1"; } // Driver code static void Main() { // Input list of strings List<string> s = new List<string>{ "abac", "zdac", "bdac" }; // Function call Console.WriteLine(FindString(s)); }} |
Javascript
// Function to find the string which only differs at one position from all given strings in the arrayfunction findString(strings) { // Get the size of the array const n = strings.length; // Get the length of a string const m = strings[0].length; // Create an object to store the frequency of each generated string const freqMap = {}; // Generate all possible strings that can be formed by changing exactly one character in each input string for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { const temp = strings[i].split(''); for (let ch = 'a'.charCodeAt(0); ch <= 'z'.charCodeAt(0); ch++) { temp[j] = String.fromCharCode(ch); const generatedString = temp.join(''); freqMap[generatedString] = (freqMap[generatedString] || 0) + 1; } } } // Traverse over the object and find the string that differs from all input strings at exactly one position for (const generatedString in freqMap) { if (freqMap[generatedString] === n && strings[0] !== generatedString) { let count = 0; for (let i = 0; i < m; i++) { if (strings[0][i] !== generatedString[i]) { count++; } } if (count === 1) { return generatedString; } } } // If no such string is found, return "-1" return "-1";}// Driver codeconst inputStrings = ["abac", "zdac", "bdac"];// Function callconsole.log(findString(inputStrings)); |
Output
adac
Time Complexity: O(N * M * 26)
Auxiliary Space: O(N * M * 26)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
