Given a space-separated string str, the task is to find the first substring whose reverse is a word in the string. All the characters of the string are lowercase English alphabet. The string ends with #. If no such substring is present, return -1
Examples:
Input: str = “mango is sweet when nam en tastes it#”
Output: man
Explanation: Substring “man” is reversed to “nam” and it is a word in the given stringInput: str = “hello world#”
Output: -1
Approach:
- Store all the words of the string on a map.
- Find all the substrings of the string.
- For each substring, check whether the reverse of the substring is a word of the string. If no such substring exists, print -1.
Below is the implementation of the above approach.
C++
// C++ program to find first substring#include <bits/stdc++.h>using namespace std;// Function to find first substringstring first_substring(string s){ int n = s.length(), c = 0; string s1, s2; map<string, int> mpp; // Storing the words present in string for (int i = 0; i < n; i++) { if (s[i] == ' ' || s[i] == '#') { s1 = s.substr(c, i - c); mpp[s1] = 1; c = i + 1; } } // Calculating for all // possible valid substring. for (int i = 0; i < n; i++) { if (s[i] == ' ') { continue; } for (int j = 0; j < n; j++) { if (s[j] == ' ') { break; } s1 = s.substr(i, j - i + 1); s2 = s1; reverse(s1.begin(), s1.end()); if (mpp[s1]) { return s2; } } } return "-1";}// Driver codeint main(){ string s, s1; s = "mango is sweet when nam en tastes it#"; s1 = first_substring(s); cout << s1 << "\n"; return 0;} |
Java
// Java program to find first subStringimport java.util.*;class GFG{// Function to find first subStringstatic String first_subString(String s){ int n = s.length(), c = 0; String s1, s2; HashMap<String, Integer> mpp = new HashMap<String, Integer>(); // Storing the words present in String for (int i = 0; i < n; i++) { if (s.charAt(i) == ' ' || s.charAt(i) == '#') { s1 = s.substring(c, i); mpp.put(s1, 1); c = i + 1; } } // Calculating for all // possible valid subString. for (int i = 0; i < n; i++) { if (s.charAt(i) == ' ') { continue; } for (int j = 0; j < n; j++) { if (s.charAt(i) == ' ') { break; } s1 = s.substring(i, j - i + 1); s2 = s1; s1 = reverse(s1); if (mpp.containsKey(s1)) { return s2; } } } return "-1";}static String reverse(String input) { char[] a = input.toCharArray(); int l, r = a.length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a);}// Driver codepublic static void main(String[] args){ String s, s1; s = "mango is sweet when nam en tastes it#"; s1 = first_subString(s); System.out.print(s1+ "\n");}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to find first substring # Function to find first substring def first_substring(s) : n = len(s); c = 0; mpp = {}; # Storing the words present in string for i in range(n) : if (s[i] == ' ' or s[i] == '#') : s1 = s[c: i]; mpp[s1] = 1; c = i + 1; # Calculating for all # possible valid substring. for i in range(n) : if (s[i] == ' ') : continue; for j in range(n) : if (s[j] == ' ') : break; s1 = s[i : j + 1]; s2 = s1; s1 = s1[::-1]; if s1 in mpp : if mpp[s1] : return s2; return "-1"; # Driver code if __name__ == "__main__" : s = "mango is sweet when nam en tastes it#"; s1 = first_substring(s); print(s1); # This code is contributed by AnkitRai01 |
C#
// C# program to find first subStringusing System;using System.Collections.Generic;class GFG{// Function to find first subStringstatic String first_subString(String s){ int n = s.Length, c = 0; String s1, s2; Dictionary<String, int> mpp = new Dictionary<String, int>(); // Storing the words present in String for (int i = 0; i < n; i++) { if (s[i] == ' ' || s[i] == '#') { s1 = s.Substring(c, i - c); mpp.Add(s1, 1); c = i + 1; } } // Calculating for all // possible valid subString. for (int i = 0; i < n; i++) { if (s[i] == ' ') { continue; } for (int j = 0; j < n; j++) { if (s[i] == ' ') { break; } s1 = s.Substring(i, j - i + 1); s2 = s1; s1 = reverse(s1); if (mpp.ContainsKey(s1)) { return s2; } } } return "-1";}static String reverse(String input) { char[] a = input.ToCharArray(); int l, r = a.Length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("", a);}// Driver codepublic static void Main(String[] args){ String s, s1; s = "mango is sweet when nam en tastes it#"; s1 = first_subString(s); Console.Write(s1 + "\n");}}// This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to find first substring// Function to find first substringfunction first_substring(s){ var n = s.length, c = 0; var s1, s2; var mpp = new Map(); // Storing the words present in string for (var i = 0; i < n; i++) { if (s[i] == ' ' || s[i] == '#') { s1 = s.substring(c, i); mpp.set(s1, 1); c = i + 1; } } // Calculating for all // possible valid substring. for (var i = 0; i < n; i++) { if (s[i] == ' ') { continue; } for (var j = 0; j < n; j++) { if (s[j] == ' ') { break; } s1 = s.substring(i, j + 1); s2 = s1; s1 = s1.split('').reverse().join(''); if (mpp.has(s1)) { return s2; } } } return "-1";}// Driver codevar s, s1;s = "mango is sweet when nam en tastes it#";s1 = first_substring(s);document.write( s1 );</script> |
Output:
man
Time complexity: O(n2) where n is length of string
Auxiliary space: O(n) as it is using extra space for map mpp
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!
