Given a string of lowercase alphabets, the task is to find indexes of a substring with given power. Assume power of a to be 1, b to be 2, c to be 3 and so on. Here the power of a substring means the sum of the powers of all the characters in that particular substring.
Examples:
Input: str = “neveropen” power = 36
Output: Substring from index 3 to 5 has power 36Explanation: k = 11, s = 19, f = 6 i.e. k + s + e = 36.
Input: str = “aditya” power = 2
Output: No substring with given power exists.
Simple Approach:
- Calculate powers of all substrings using nested for loops.
- If the power of any substring equals the given power then print the indexes of the substring.
- If no such substring exists then print “No substring with given power exists”.
Time Complexity: O (n ^ 2).
Efficient Approach: Use map to store the powers.
- For each element check if curr_power – power exists in the map or not.
- If it exists in the map it means that we have a substring present with given power, else we insert curr_power into the map and proceed to the next character.
- If all characters of the string are processed and we didn’t find any substring with given power, then substring doesn’t exist.
Implementation:
C++
// C++ program to find substring with given power#include <bits/stdc++.h>#define ll long long intusing namespace std;// Function to print indexes of substring with// power as given power.void findSubstring(string str, ll power){ ll i; // Create an empty map unordered_map<ll, ll> map; // Maintains sum of powers of characters so far. int curr_power = 0; int len = str.length(); for (i = 0; i < len; i++) { // Add current character power to curr_power. curr_power = curr_power + (str[i] - 'a' + 1); // If curr_power is equal to target power // we found a substring starting from index 0 // and ending at index i. if (curr_power == power) { cout << "Substring from index " << 0 << " to " << i << " has power " << power << endl; return; } // If curr_power - power already exists in map // then we have found a subarray with target power. if (map.find(curr_power - power) != map.end()) { cout << "Substring from index " << map[curr_power - power] + 1 << " to " << i <<" has power " <<power << endl; return; } map[curr_power] = i; } // If we reach here, then no substring exists. cout << "No substring with given power exists.";}// Drivers codeint main(){ string str = "neveropen"; ll power = 36; findSubstring(str, power); return 0;} |
Java
// Java program to find substring with given powerimport java.util.*;class GFG { // Function to print indexes of substring with // power as given power. static void findSubstring(String str, int power) { // Create an empty map HashMap<Integer, Integer> map = new HashMap<>(); // Maintains sum of powers of characters so far. int curr_power = 0; int len = str.length(); for (int i = 0; i < len; i++) { // Add current character power to curr_power. curr_power = curr_power + (str.charAt(i) - 'a' + 1); // If curr_power is equal to target power // we found a substring starting from index 0 // and ending at index i. if (curr_power == power) { System.out.println("Substring from index 0" + " to " + i + " has power " + power); return; } // If curr_power - power already exists in map // then we have found a subarray with target power. if (map.containsKey(curr_power - power)) { System.out.println("Substring from index " + (map.get(curr_power - power) + 1) + " to " + i + " has power " + power); return; } map.put(curr_power, i); } // If we reach here, then no substring exists. System.out.println("No substring with given power exists."); } // Driver Code public static void main(String[] args) { String str = "neveropen"; int power = 36; findSubstring(str, power); }}// This code is contributed by// sanjeev2552 |
Python3
# Python program to find substring with given power# Function to print indexes of substring with# power as given power.def findSubstring(Str,power): map = {} # Maintains sum of powers of characters so far. curr_power = 0 Len = len(Str) for i in range(Len): # Add current character power to curr_power. curr_power = curr_power + (ord(Str[i]) - ord('a') + 1) # If curr_power is equal to target power # we found a substring starting from index 0 # and ending at index i. if (curr_power == power): print("Substring from index 0 to " + str(i) + " has power " + str(power)) return # If curr_power - power already exists in map # then we have found a subarray with target power. if (curr_power - power in map): print("Substring from index " +str(map[curr_power - power] + 1) + " to " + str(i) + " has power " + str(power)) return map[curr_power] = i # If we reach here, then no substring exists. print("No substring with given power exists.")# Driver CodeStr = "neveropen"power = 36findSubstring(Str, power)# This code is contributed by shinjanpatra |
C#
// C# program to find substring// with given powerusing System;using System.Collections.Generic;class GFG { // Function to print indexes of substring // with power as given power. static void findSubstring(String str, int power) { // Create an empty map Dictionary<int, int> map = new Dictionary<int, int>(); // Maintains sum of powers // of characters so far. int curr_power = 0; int len = str.Length; for (int i = 0; i < len; i++) { // Add current character power // to curr_power. curr_power = curr_power + (str[i] - 'a' + 1); // If curr_power is equal to target power // we found a substring starting from index 0 // and ending at index i. if (curr_power == power) { Console.WriteLine("Substring from index 0" + " to " + i + " has power " + power); return; } // If curr_power - power already exists in map // then we have found a subarray with target power. if (map.ContainsKey(curr_power - power)) { Console.WriteLine("Substring from index " + (map[curr_power - power] + 1) + " to " + i + " has power " + power); return; } if (!map.ContainsKey(curr_power)) map.Add(curr_power, i); else map[curr_power] = i; } // If we reach here, then no substring exists. Console.WriteLine("No substring with " + "given power exists"); } // Driver Code public static void Main(String[] args) { String str = "neveropen"; int power = 36; findSubstring(str, power); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to find substring with given power// Function to print indexes of substring with // power as given power.function findSubstring(str,power){ let map = new Map(); // Maintains sum of powers of characters so far. let curr_power = 0; let len = str.length; for (let i = 0; i < len; i++) { // Add current character power to curr_power. curr_power = curr_power + (str[i].charCodeAt(0) - 'a'.charCodeAt(0) + 1); // If curr_power is equal to target power // we found a substring starting from index 0 // and ending at index i. if (curr_power == power) { document.write("Substring from index 0" + " to " + i + " has power " + power+"<br>"); return; } // If curr_power - power already exists in map // then we have found a subarray with target power. if (map.has(curr_power - power)) { document.write("Substring from index " + (map.get(curr_power - power) + 1) + " to " + i + " has power " + power+"<br>"); return; } map.set(curr_power, i); } // If we reach here, then no substring exists. document.write("No substring with given power exists.<br>");}// Driver Codelet str = "neveropen";let power = 36;findSubstring(str, power);// This code is contributed by rag2127</script> |
Output
Substring from index 3 to 5 has power 36
Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: O(n)
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!
