mixing-strings-1

Heisenberg is very fond of mixing various strings together. But he has storage problem. 
He wants that his strings use as less space as possible. 

He has N strings right now. He wants to store them together. 
To reduce space he can use this property of mixing two strings:

Suppose he has string A="abcdef" and B="cdefghi". 
He can mix them to form "abcdefghi".

So, two strings can be mixed if some substring at the end of A is also at the starting of B which are mixed together.

Given the list of strings he has right now, print the minimum final characters he can get if he can mix any number of times, any of the given strings or the intermediate strings.

Input:

First line contains N, the number of strings.
Next N line contains, one string per line.

Output:

Print in one line the minimum final characters he can get if he can mix any number of times, any of the given strings or the intermediate strings.

Constraints:

1 ≤ N ≤ 8

1≤ Length of each string ≤ 15

SAMPLE INPUT
2
abcdef
fghi

SAMPLE OUTPUT
9

Source: hackerearth | Difficulty: EASY
Tags: Data structures

Implementation

Complete search


Solutions:
from itertools import permutations
l=[]
o=[]
n=eval(input())
for i in range(n):
	a=input()
	l.append(a)
p=permutations(l)
for st in p:
	opt = st[0]
	for j in range(1,n):
		indices = [i for i, x in enumerate(opt) if x == st[j][0]]
	
		flag = 1
		for ind in indices:
			if opt[ind:] == st[j][0:len(opt[ind:])]:
				opt = opt+st[j][len(opt[ind:]):]
				flag = 0
				break
		if flag:
			opt = opt+st[j]
 
	o.append(len(opt))
 
print(min(o))


import sys,itertools

n=int(eval(input()))
li=[]
while n>0:
	s=sys.stdin.readline().strip()
	li.append(s)
	n=n-1

mi=9999999999
for l in itertools.permutations(li,len(li)):
 r=l[0]
 for i in range(1,len(l)):
		 f=0
		 for j in range(0,len(r)):
				s1=r[j:]
				if len(s1)<=len(l[i]):
					  if s1==l[i][0:len(s1)]:
							 r=r+l[i][len(s1):]
							 f=1
							 break
		 if f==0:
				 r=r+l[i]
 if mi>len(r):
	  mi=len(r) 

print(mi)
		 
				


def suture(s1, s2):
	for n in range(len(s2), 0, -1):
		if s1.endswith(s2[:n]):
			return s1 + s2[n:]
	return s1 + s2

import itertools
strings = []
for _ in range(eval(input())):
	strings.append(input())
best = 10**100
for perm in itertools.permutations(strings):
	line = ''
	for s in perm:
		line = suture(line, s)
	if len(line) < best:
		best = len(line)
print(best)


n = int(input())

stg = []

for i in range(n):
	stg.append(input())

output = []

#finding all permutations
from itertools import permutations

per = permutations(stg)

for st in per:
	opt = st[0]
	for j in range(1,n):
		indices = [i for i, x in enumerate(opt) if x == st[j][0]]
	
		flag = 1
		for ind in indices:
			if opt[ind:] == st[j][0:len(opt[ind:])]:
				opt = opt+st[j][len(opt[ind:]):]
				flag = 0
				break
		if flag:
			opt = opt+st[j]

	output.append(len(opt))

print(min(output))