Given a starting string X of 3 characters, finishing string Y of 3 characters and an array of forbidden strings. The task is to find the minimum number of clicks to reach Y from X.
Rules:
- Each of the 3 characters changes in a circular manner i.e. on each click you can go from either a to b or a to z and none of the forbidden words is ever displayed.
- If it is not possible to reach Y, print -1. In each click, only a single letter can be changed.
- Each forbidden string is of the form: {“S1” “S2” “S3”} where each string Si contains forbidden letters for that character.
- Forbidden string = {“ac” “bx” “lw”} implies words “abl”, “cxw”, “cbl”, “abw”, “cbw”, “axl”, “axw” and “cxl” are forbidden and will never be displayed.
Note: If the starting string X is also a possible combination of forbidden characters, then also the result should be -1.
Input: X = “znw”, Y = “lof”, N = 4 (no of forbidden strings)
forbidden =
{ ” qlb “, ” jcm “, ” mhoq ” },
{ ” azn “, ” piy “, ” vj ” },
{ ” by “, ” oy “, ” ubo ” },
{ ” jqm “, ” f “, ” ej ” }
Output: Minimum no of clicks required is 22
Explanation: Since no combination out of the given forbidden strings forms the final string Y, so the string Y becomes valid.Thus minimum number of clicks required is computed as:
z – l in forward direction by 12 clicks
z – l in backward direction by 14 clicks
n – o in forward direction by 1 click
n – o in backward direction by 25 clicks
w – f in forward direction by 9 clicks
w – f in backward direction by 17 clicksTotal minimum clicks = 12 + 1 + 9 = 22.
Input: X = “bdb”, Y = “xxx”, N = 1 (no of forbidden strings)
forbidden = { ” ax “, ” acx “, ” bxy ” }
Output: Minimum no of clicks required is -1
Explanation: As “xxx” is a possible combination of forbidden characters, therefore it is not possible to reach Y from X.
Approach:
Use BFS(Breadth First Search) with certain modifications in order to get the min number of clicks, bypassing the forbidden strings.
- Since each of the 3 positions can contain alphabets, hence create a 3D visited array of dimensions 26 * 26 * 26 in order to traverse the word states.
- To visualize each of the restricted words, create another 3D array of dimensions 26 * 26 * 26 to keep track of the words which must never be visited in the traversal.
- Since each of the 3 characters changes in a circular manner i.e, letters will change in a circular fashion on each click, there is a need to take care to modulo 26 every time the next letter is reached.
- Let current state of word be [X Y Z]. Then on a single click movement, the 6 states are possible.
- Hence create 3 utility arrays dx, dy, dz to keep the traversal a streamlined process. Store each word state in a struct having 4 fields namely a, b, c (each of the 3 characters) and distance from the starting words.
- The six stare are following:
[ X+1 Y Z ], [ X-1 Y Z ], [ X Y+1 Z ], [ X Y-1 Z ], [ X Y Z+1 ], [ X Y Z-1 ].
Below is the implementation of above approach:
C++
// C++ code for above program.#include <bits/stdc++.h>using namespace std;#define int long long int// each node represents a word statestruct node { int a, b, c; // dist from starting word X int dist;};// 3D visited arraybool visited[26][26][26];// 3D restricted arraybool restricted[26][26][26];// utility arrays for single step// traversal in left and rightint dx[6] = { 1, -1, 0, 0, 0, 0 };int dy[6] = { 0, 0, 1, -1, 0, 0 };int dz[6] = { 0, 0, 0, 0, 1, -1 };// function to find the// minimum clicks.void solve(string start, string end, int qx, const vector<vector<string> >& forbidden){ memset(visited, 0, sizeof(visited)); memset(restricted, 0, sizeof(restricted)); for (auto vec : forbidden) { string a = vec[0]; string b = vec[1]; string c = vec[2]; for (auto x : a) for (auto y : b) for (auto z : c) { // each invalid word is // decoded and marked as // restricted = true. restricted[x - 'a'] [y - 'a'] [z - 'a'] = true; } } // starting and ending letter a int sa = start[0] - 'a'; int ea = end[0] - 'a'; // starting and ending letter b int sb = start[1] - 'a'; int eb = end[1] - 'a'; // starting and ending letter c int sc = start[2] - 'a'; int ec = end[2] - 'a'; if (restricted[sa][sb][sc] or restricted[ea][eb][ec]) { // check if starting word // or finishing word is // restricted or not cout << -1 << endl; return; } // queue of nodes for BFS queue<node> q; // initial starting word pushed in // queue. dist = 0 for starting word q.push({ sa, sb, sc, 0 }); // mark as visited visited[sa][sb][sc] = true; while (!q.empty()) { node x = q.front(); q.pop(); // final destination reached condition if (x.a == (end[0] - 'a') and x.b == (end[1] - 'a') and x.c == (end[2] - 'a')) { cout << x.dist << endl; return; } int DIST = x.dist; for (int i = 0; i < 6; i++) { // mod 26 for circular letter sequence // next letter for a int A = (x.a + dx[i] + 26) % 26; // next letter for b int B = (x.b + dy[i] + 26) % 26; // next letter for c int C = (x.c + dz[i] + 26) % 26; if (!restricted[A][B][C] and !visited[A][B][C]) { // if a valid word state, // push into queue q.push({ A, B, C, DIST + 1 }); visited[A][B][C] = true; } } } // reach here if not possible // to reach final word Y cout << -1 << endl;}// Driver Codesigned main(){ // starting string string X = "znw"; // final string string Y = "lof"; // no of restricting word vectors int N = 4; vector<vector<string> > forbidden = { { "qlb", "jcm", "mhoq" }, { "azn", "piy", "vj" }, { "by", "oy", "ubo" }, { "jqm", "f", "ej" } }; solve(X, Y, N, forbidden); return 0;} |
Java
// Java code addition import java.io.*;import java.util.*;public class GFG { // each node represents a word state static class Node { int a, b, c; // dist from starting word X int dist; public Node(int a, int b, int c, int dist) { this.a = a; this.b = b; this.c = c; this.dist = dist; } } // 3D visited array static boolean[][][] visited = new boolean[26][26][26]; // 3D restricted array static boolean[][][] restricted = new boolean[26][26][26]; // utility arrays for single step // traversal in left and right static int[] dx = { 1, -1, 0, 0, 0, 0 }; static int[] dy = { 0, 0, 1, -1, 0, 0 }; static int[] dz = { 0, 0, 0, 0, 1, -1 }; // function to find the minimum clicks. public static void solve(String start, String end, int qx, final ArrayList<ArrayList<String>> forbidden) { Arrays.fill(visited[0][0], false); Arrays.fill(restricted[0][0], false); for (ArrayList<String> vec : forbidden) { String a = vec.get(0); String b = vec.get(1); String c = vec.get(2); for (char x : a.toCharArray()) for (char y : b.toCharArray()) for (char z : c.toCharArray()) { // each invalid word is // decoded and marked as // restricted = true. restricted[x - 'a'] [y - 'a'] [z - 'a'] = true; } } // starting and ending letter a int sa = start.charAt(0) - 'a'; int ea = end.charAt(0) - 'a'; // starting and ending letter b int sb = start.charAt(1) - 'a'; int eb = end.charAt(1) - 'a'; // starting and ending letter c int sc = start.charAt(2) - 'a'; int ec = end.charAt(2) - 'a'; if (restricted[sa][sb][sc] || restricted[ea][eb][ec]) { // check if starting word // or finishing word is // restricted or not System.out.println(-1); return; } // queue of nodes for BFS Queue<Node> q = new LinkedList<Node>(); // initial starting word pushed in // queue. dist = 0 for starting word q.add(new Node(sa, sb, sc, 0)); // mark as visited visited[sa][sb][sc] = true; while (!q.isEmpty()) { Node x = q.poll(); // final destination reached condition if (x.a == (end.charAt(0) - 'a') && x.b == (end.charAt(1) - 'a') && x.c == (end.charAt(2) - 'a')) { System.out.println(x.dist); return; } int DIST = x.dist; for (int i = 0; i < 6; i++) { // mod 26 for circular letter sequence // next letter for a int A = (x.a + dx[i] + 26) % 26; // next letter for b int B = (x.b + dy[i] + 26) % 26; // next letter for c int C = (x.c + dz[i] + 26) % 26; if (!restricted[A][B][C] && !visited[A][B][C]) { // if a valid word state, // push into queue q.add(new Node(A, B, C, DIST + 1 )); visited[A][B][C] = true; } } } // reach here if not possible // to reach final word Y System.out.println(-1); } // Driver Code public static void main(String[] args) { // starting string String X = "znw"; // final string String Y = "lof"; // no of restricting word vectors int N = 4; ArrayList<ArrayList<String>> forbidden = new ArrayList<ArrayList<String>>(3); // Adding elements to the 2D ArrayList forbidden.add(new ArrayList<String>(Arrays.asList("qlb", "jcm", "mhoq" ))); forbidden.add(new ArrayList<String>(Arrays.asList("azn", "piy", "vj"))); forbidden.add(new ArrayList<String>(Arrays.asList("by", "oy", "ubo"))); forbidden.add(new ArrayList<String>(Arrays.asList( "jqm", "f", "ej"))); solve(X, Y, N, forbidden); } }// The code is contributed by Arushi Goel. |
Python3
# Python code for above program.from collections import dequedx = [1, -1, 0, 0, 0, 0]dy = [0, 0, 1, -1, 0, 0]dz = [0, 0, 0, 0, 1, -1]# each node represents a word stateclass Node: def __init__(self, a, b, c, dist): self.a = a self.b = b self.c = c # dist from starting word X self.dist = dist# function to find the# minimum clicks.def solve(start, end, qx, forbidden): visited = [[[False for _ in range(26)] for _ in range(26)] for _ in range(26)] restricted = [[[False for _ in range(26)] for _ in range(26)] for _ in range(26)] for a, b, c in forbidden: for x in a: for y in b: for z in c: # each invalid word is # decoded and marked as # restricted = true. restricted[ord(x) - ord('a')][ord(y) - ord('a')][ord(z) - ord('a')] = True # starting and ending letter a sa, ea = ord(start[0]) - ord('a'), ord(end[0]) - ord('a') # starting and ending letter b sb, eb = ord(start[1]) - ord('a'), ord(end[1]) - ord('a') # starting and ending letter c sc, ec = ord(start[2]) - ord('a'), ord(end[2]) - ord('a') if restricted[sa][sb][sc] or restricted[ea][eb][ec]: # check if starting word # or finishing word is # restricted or not print(-1) return q = deque() # initial starting word pushed in # queue. dist = 0 for starting word q.append(Node(sa, sb, sc, 0)) # mark as visited visited[sa][sb][sc] = True while q: x = q.popleft() # final destination reached condition if x.a == ea and x.b == eb and x.c == ec: print(x.dist) return DIST = x.dist for i in range(6): # mod 26 for circular letter sequence # next letter for a A = (x.a + dx[i] + 26) % 26 # next letter for b B = (x.b + dy[i] + 26) % 26 # next letter for c C = (x.c + dz[i] + 26) % 26 if not restricted[A][B][C] and not visited[A][B][C]: # if a valid word state, # push into queue q.append(Node(A, B, C, DIST + 1)) visited[A][B][C] = True # reach here if not possible # to reach final word Y print(-1)# Driver Code# starting stringX = "znw"# final stringY = "lof"# no of restricting word vectorsN = 4forbidden = [["qlb", "jcm", "mhoq"], ["azn", "piy", "vj"], ["by", "oy", "ubo"], ["jqm", "f", "ej"]]solve(X, Y, N, forbidden) |
C#
// C#// each node represents a word state code for above program.using System;using System.Collections.Generic;// each node represents a word statepublic struct Node{ public int a, b, c; // dist from starting word X public int dist;}public class Program{ public static void Solve(string start, string end, int N, List<List<string>> forbidden) { // 3D visited array bool[,,] visited = new bool[26,26,26]; // 3D restricted array bool[,,] restricted = new bool[26,26,26]; foreach (List<string> vec in forbidden) { string a = vec[0]; string b = vec[1]; string c = vec[2]; foreach (char x in a) { foreach (char y in b) { foreach (char z in c) { // each invalid word is // decoded and marked as // restricted = true. // starting and ending letter a restricted[x - 'a', y - 'a', z - 'a'] = true; } } } } // starting and ending letter a int sa = start[0] - 'a'; int ea = end[0] - 'a'; // starting and ending letter b int sb = start[1] - 'a'; int eb = end[1] - 'a'; // starting and ending letter c int sc = start[2] - 'a'; int ec = end[2] - 'a'; if (restricted[sa, sb, sc] || restricted[ea, eb, ec]) { // check if starting word // or finishing word is // restricted or not Console.WriteLine("-1"); return; } // queue of nodes for BFS Queue<Node> q = new Queue<Node>(); // initial starting word pushed in // queue. dist = 0 for starting word q.Enqueue(new Node { a = sa, b = sb, c = sc, dist = 0 }); // mark as visited visited[sa, sb, sc] = true; while (q.Count > 0) { Node x = q.Dequeue(); // final destination reached condition if (x.a == ea && x.b == eb && x.c == ec) { Console.WriteLine(x.dist); return; } int DIST = x.dist; // utility arrays for single step// traversal in left and right int[] dx = { 1, -1, 0, 0, 0, 0 }; int[] dy = { 0, 0, 1, -1, 0, 0 }; int[] dz = { 0, 0, 0, 0, 1, -1 }; for (int i = 0; i < 6; i++) { // mod 26 for circular letter sequence // next letter for a int A = (x.a + dx[i] + 26) % 26; // next letter for b int B = (x.b + dy[i] + 26) % 26; // next letter for c int C = (x.c + dz[i] + 26) % 26; if (!restricted[A, B, C] && !visited[A, B, C]) { q.Enqueue(new Node { a = A, b = B, c = C, dist = DIST + 1 }); visited[A, B, C] = true; } } } // reach here if not possible // to reach final word Y Console.WriteLine("-1"); } // Driver Code public static void Main() { // starting string string X = "znw"; // final string string Y = "lof"; // no of restricting word vectors int N = 4; List<List<string>> forbidden = new List<List<string>> { new List<string>{"qlb", "jcm", "mhoq"}, new List<string>{"azn", "piy", "vj"}, new List<string>{"by", "oy", "ubo"}, new List<string>{"jqm", "f", "ej"} }; Solve(X, Y, N, forbidden); }} |
Javascript
// JavaScript code for above program.const dx = [1, -1, 0, 0, 0, 0];const dy = [0, 0, 1, -1, 0, 0];const dz = [0, 0, 0, 0, 1, -1];// each node represents a word stateclass Node { constructor(a, b, c, dist) { this.a = a; this.b = b; this.c = c; // dist from starting word X this.dist = dist; }}// function to find the minimum clicks.function solve(start, end, forbidden) { const visited = Array.from({ length: 26 }, () => Array.from({ length: 26 }, () => Array.from({ length: 26 }, () => false)) ); const restricted = Array.from({ length: 26 }, () => Array.from({ length: 26 }, () => Array.from({ length: 26 }, () => false)) ); for (const [a, b, c] of forbidden) { for (const x of a) { for (const y of b) { for (const z of c) { // each invalid word is // decoded and marked as // restricted = true. restricted[x.charCodeAt() - 97][y.charCodeAt() - 97][ z.charCodeAt() - 97 ] = true; } } } } // starting and ending letter a const sa = start.charCodeAt(0) - 97; const ea = end.charCodeAt(0) - 97; // starting and ending letter b const sb = start.charCodeAt(1) - 97; const eb = end.charCodeAt(1) - 97; // starting and ending letter c const sc = start.charCodeAt(2) - 97; const ec = end.charCodeAt(2) - 97; if (restricted[sa][sb][sc] || restricted[ea][eb][ec]) { // check if starting word or finishing word is restricted or not console.log(-1); return; } const q = []; // initial starting word pushed in queue. dist = 0 for starting word q.push(new Node(sa, sb, sc, 0)); // mark as visited visited[sa][sb][sc] = true; while (q.length > 0) { const x = q.shift(); // final destination reached condition if (x.a === ea && x.b === eb && x.c === ec) { console.log(x.dist); return; } const DIST = x.dist; for (let i = 0; i < 6; i++) { // mod 26 for circular letter sequence // next letter for a const A = ((x.a + dx[i] + 26) % 26) | 0; // next letter for b const B = ((x.b + dy[i] + 26) % 26) | 0; // next letter for c const C = ((x.c + dz[i] + 26) % 26) | 0; if (!restricted[A][B][C] && !visited[A][B][C]) { // if a valid word state, push into queue q.push(new Node(A, B, C, DIST + 1)); visited[A ][B][C] = true; } } } // reach here if not possible to reach final word Y console.log(-1);}// Driver Code// starting stringconst X = "znw";// final stringconst Y = "lof";// no of restricting word vectorsconst N = 4;const forbidden = [ ["qlb", "jcm", "mhoq"], ["azn", "piy", "vj"], ["by", "oy", "ubo"], ["jqm", "f", "ej"],];solve(X, Y, forbidden); |
Output
22
Time Complexity: O(26 * 26 * 26), since at max, there can be 26*26*26 word states.
Space Complexity: O(26 * 26 * 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!
