Home
hackerrank
hackerrank certification

File Renaming - Problem Solving (Intermediate) | HackerRank

 



File Renaming

You want to rename a certain file on your computer. However, because of a glitch, you can't rename it to whatever you want-you can only delete characters from the old file name. In other words, the new file name must be a subsequence of the original file name. Given the original file name, as well as the file name you'd like to change it to, how many ways are there to create the new file name by just removing characters?
Note: Because the number of ways may be large, return the answer modulo 109 +7.


For example, let's say you want the new file name to be newName = "aba". Currently, the oldName = "ababa". There are a total of 4 subsequences within the old file name that would form the new file name:

    • "ababa"
    • "ababa"
    • "ababa"
    • "ababa"

Therefore, the answer is 4 modulo 109+7


Function Description 

Complete the function renameFile in the editor below. The function must return an integer denoting the number of ways to find newName within oldName modulo 109+7.

rename File has the following parameters:
    newName, a string
    oldName, a string


Constraints

    • 1 <length of oldName < 105

Input Format For Custom Testing

The first line contains a string, newName, denoting the desired new file name.
The second line contains a string, oldName, denoting the original file name.

Solution in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#!/bin/python3

import math
import os
import random
import re
import sys



#
# Complete the 'renameFile' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. STRING newName
#  2. STRING oldName
#

def renameFile(newName, oldName):
    n = len(newName)
    m = len(oldName)
    dp = [1 for j in range(m + 1)]
    for i in range(1, n + 1):
        dpp = [0 for _ in range(m + 1)]
        for j in range(i, m + 1):
            dpp[j] = dpp[j - 1]
            if newName[i - 1] == oldName[j - 1]:
                dpp[j] += dp[j - 1]
        dp = dpp
    return dp[-1] % (10**9 + 7)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    newName = input()

    oldName = input()

    result = renameFile(newName, oldName)

    fptr.write(str(result) + '\n')

    fptr.close()

Labels : #hackerrank ,#hackerrank certification ,#problem solving ,#problem solving (intermediate) ,#python ,

Post a Comment