Find sub-string with given power

0 0 6 minutes read

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 = “zambiatek” power = 36
Output: Substring from index 3 to 5 has power 36

Explanation: 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 int
using 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 code
int main()
{
    string str = "zambiatek";
    ll power = 36;
 
    findSubstring(str, power);
 
    return 0;
}

Java

// Java program to find substring with given power
import 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 = "zambiatek";
        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 Code
Str = "zambiatek"
power = 36
 
findSubstring(Str, power)
 
# This code is contributed by shinjanpatra

C#

// C# program to find substring
// with given power
using 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 = "zambiatek";
        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 Code
let str = "zambiatek";
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 zambiatek!