Shift String

3

2 votes
Breadth-first search, Algorithms, Dynamic Programming and Bit Masking, Brute-force search, String, Dynamic Programming, Bitmask
Problem

Given a string, s, of length, n, and a list of m strings, x1,x2,...,xm.  All m strings in the list are distinct and have length n i.e i|xi|=n, and none of the given strings is equal to s.

You can perform any number of operations s.

In an operation you are allowed to choose one position in the string, s, and change the character at the position to the next or previous character in the English alphabet cyclically ('a' -> 'b', 'b' -> 'c', 'c' -> 'd', ..., 'z' -> 'a', 'b' -> 'a', ...).

What is the minimum number of operations that you have to perform on, s, so for all the given m strings, s becomes xi at least once after one of the performed operations. 

 

INPUT FORMAT 

The first line of the input contains an integer, n (1<=n<=5)   - denoting the length of the string s

The second line of the input contains a string, s - denoting the string which you can perform operations on. Each character in s is a lowercase English alphabet ('a' - 'z'). 

The next line of the input contains an integer, m (1<=m<=15) - denoting the number of strings that will be in the list.

The next m lines distinct strings, xi (|xi|=n, xis)   - denoting a string in the list. Each character in xi is a lowercase english alphabet ('a' - 'z')

 

OUTPUT FORMAT 

The output should contain one line denoting the minimum amount of operations that need to be performed on s, to reach each of the m strings at least once. 

Sample Input
3
abc
3
zbe
zbc
abd
Sample Output
5
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In the sample input, s = abc, and we have 3 strings zbe, zbc, and abd, that s must become at least once, in one of the operations. 

One way of reaching all 3 strings using the minimum number of operations is: 

  • OPERATION 1: shift index 2 (0-indexed) in s forward, s becomes = "abd" (s has now become x3)
  • OPERATION 2: shift index 0 (0-indexed) in s backward, s becomes = "zbd".
  • OPERATION 3: shift index 2 (0-indexed) in s forward, s becomes = "zbe" (s has now become x1).
  • OPERATION 4: shift index 2 (0-indexed) in s backward, s becomes "zbd".
  • OPERATION 5: shift index 2 (0-indexed) in s backward, s becomes "zbc" (s has now become x2).

It is not possible to reach all 3 strings using less than 5 operations. Hence, the answer to this input is 5.

Editor Image

?