Codeforces: B. New Problem

The problem is from codeforces: http://www.codeforces.com/problemset/problem/278/B

The problem asks for the first sequence (sorted in alphabetic order) of character(s) that is not a substring of the given list of strings.The maximum number of strings given as input is 30, with each length at most 20 characters, that is 600 characters.There are 26 possibilities for single character, and 26 X 26 combinations for 2 characters, thus the total is 702 cases, larger than the input.

Therefore, to check combinations with length smaller or equal to 2 is enough. We can use two boolean arrays to  store whether the sequences have appeared.

#!/usr/bin/env python
# https://helloacm.com

n = int(raw_input())

a = [False] * 26
ab = [False] * 26 * 26

for x in xrange(n):
    s = raw_input()
    for y in s:
        a[ord(y) - 97] = True
    for i in xrange(len(s) - 1):
        ab[(ord(s[i]) - 97) * 26 + ord(s[i + 1]) - 97] = True

found = False
for x in xrange(26):
    if a[x] == False:
        found = True
        print chr(97 + x)
        break

if not found:
    for x in range(26 * 26):
        if not ab[x]:
            print chr(97 + x / 26) + chr(97 + x % 26)
            break

We can use a set to accomplish the same task.

n  = int(input())
ss =[raw_input().rstrip() for i in range(n)]
se = set()
for s in ss:
    for i in range(len(s)):
        se.add(s[i])
    for i in range(0,len(s)):
        se.add(s[i:i+2])
for i in range(26):
    if chr(i+ord('a')) not in se:
        print chr(i+ord('a'))
        exit()
for i in range(26):
    for j in range(26):
        nc = chr(i+ord('a'))+chr(j+ord('a'))
        if nc not in se:
            print nc
            exit()

Or even shorter,

n = input()
s = ' '.join(raw_input() for i in xrange(n))
abc = [chr(i + ord('a')) for i in xrange(26)]
abc += [a + b for a in abc for b in abc]
print filter(lambda t: not t in s, abc)[0]

And this is also the solution.

s=[raw_input()for i in range(input())]
c=[chr(i+97)for i in range(26)]
for x in c:
	if sum(t.count(x)for t in s)==0:
		print x
		exit()
for x in c:
	for y in c:
		if sum(t.count(x+y)for t in s)==0:
			print x+y
			exit()

The python way:

import sys

inp = sys.stdin.read().strip().splitlines()[1:]

def advance(s):
    if s == '':
        return 'a'
    elif s[-1] == 'z':
        return advance(s[:-1]) + 'a'
    else:
        return s[:-1] + chr(ord(s[-1]) + 1)

res = 'a'
while reduce(lambda x, y: x or y, [res in i for i in inp]):
    res = advance(res)

sys.stdout.write(res)

The DFS (Depth-First-Search) method:

n=input()
st=set()
for _ in xrange(n):
    s=raw_input()
    l = len(s)
    for x in xrange(1,l+1):
        for i in xrange(0,l):
            st.add(s[i:i+x])

def dfs(s,i,len):
    if i == len: 
        if s not in st: print s; exit()
        return
    for j in xrange(0,26):
        dfs(s+chr(ord('a')+j),i+1,len)

for x in xrange(1,21):
    s=''
    dfs(s,0,x)

–EOF (The Ultimate Computing & Technology Blog) —