Problem:


Score : 400 points

Problem Statement

In this problem, we only consider strings consisting of lowercase English letters.

Strings s and t are said to be isomorphic when the following conditions are satisfied:

|s| = |t| holds.

For every pair i, j, one of the following holds:

s_i = s_j and t_i = t_j.

s_i \neq s_j and t_i \neq t_j.

For example, abcac and zyxzx are isomorphic, while abcac and ppppp are not.

A string s is said to be in normal form when the following condition is satisfied:

For every string t that is isomorphic to s, s \leq t holds. Here \leq denotes lexicographic comparison.

For example, abcac is in normal form, but zyxzx is not since it is isomorphic to abcac, which is lexicographically smaller than zyxzx.

You are given an integer N.
Print all strings of length N that are in normal form, in lexicographically ascending order.

Constraints

1 \leq N \leq 10

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

Output

Assume that there are K strings of length N that are in normal form: w_1, \ldots, w_K in lexicographical order.
Output should be in the following format:

w_1
:
w_K

Sample Input 1

1

Sample Output 1

a

Sample Input 2

2

Sample Output 2

aa
ab



Sample input:
1


Sample output:
a

Submission status: Accepted

Solution code:
import math


data = [ "a","b","c","d","e","f","g","h","i","j" ]


result = []


def create( max_letter, remaining_depth, text ):
    if remaining_depth == 0:
        result.append(text)
        return
    
    for i in range(0,max_letter+1):
        new_text = text + data[i]
        create( max(i+1,max_letter),remaining_depth-1,new_text )
        
    
        
        





N = int(input())

create( 0,N,"")

result.sort()
for line in result:
    print(line)

Submission status: Accepted

Solution code:
def dfs(t, c_max):
    if(len(t)==n):
        print(t)
    else:
        for i in range(c_max+1):
            tmp_t = t
            tmp_t += s[i]
            # print(tmp_t)
            dfs(tmp_t,max(i+1, c_max))

s = "abcdefghijklm"
n = int(input())

dfs('a', 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import string
import sys
sys.setrecursionlimit(10 ** 7)
from functools import lru_cache

N = int(input())
alph = string.ascii_lowercase

def search(S, mx):
    if len(S) == N:
        print(S)
    else:
        for s in alph[: mx + 1]:
            search(S + s, mx)
        search(S + alph[mx + 1], mx + 1)

search('a', 0)

Submission status: Accepted

Solution code:
n = int(input())

s = ['' for i in range(n)]
def dfs(k, c):
    if k == n:
        print("".join(s))
        return
    for i in range(c):
        s[k] = chr(i+ord('a'))
        dfs(k+1, c)
    s[k] = chr(c+ord('a'))
    dfs(k+1, c+1)

dfs(0, 0)

Submission status: Accepted

Solution code:
#a,b,c = [int(x) for x in input().split()]
n = int(input())
l = [0]*n
ans = ""
al=["a","b","c","d","e","f","g","h","i","j"]
if n == 1:
  print("a")
elif n == 2:
  for x in range(2):
    l[1] = x
    for i in range(n):
      for k in range(n):
        if l[i] == k:
          ans = ans + al[k]
    print(ans)
    ans = ""
elif n == 3:
  for x in range(2):
    l[1] = x
    for a in range(max(l)+2):
      l[2] = a
      for i in range(n):
        for k in range(n):
          if l[i] == k:
            ans = ans + al[k]
      print(ans)
      ans = ""
elif n == 4:
  for x in range(2):
    l[1] = x
    for a in range(max(l)+2):
      l[2] = a
      for b in range(max(l)+2):
        l[3] = b
        for i in range(n):
          for k in range(n):
            if l[i] == k:
              ans = ans + al[k]
        print(ans)
        ans = ""
      l[3] = 0
    l[2] = 0
elif n == 5:
  for x in range(2):
    l[1] = x
    for a in range(max(l)+2):
      l[2] = a
      for b in range(max(l)+2):
        l[3] = b
        for c in range(max(l)+2):
          l[4] = c        
          for i in range(n):
            for k in range(n):
              if l[i] == k:
                ans = ans + al[k]
          print(ans)
          ans = ""
        l[4] = 0
      l[3] = 0
    l[2] = 0
elif n == 6:
  for x in range(2):
    l[1] = x
    for a in range(max(l)+2):
      l[2] = a
      for b in range(max(l)+2):
        l[3] = b
        for c in range(max(l)+2):
          l[4] = c
          for d in range(max(l)+2):
            l[5] = d
            for i in range(n):
              for k in range(n):
                if l[i] == k:
                  ans = ans + al[k]
            print(ans)
            ans = ""
          l[5] = 0
        l[4] = 0
      l[3] = 0
    l[2] = 0            
elif n == 7:
  for x in range(2):
    l[1] = x
    for a in range(max(l)+2):
      l[2] = a
      for b in range(max(l)+2):
        l[3] = b
        for c in range(max(l)+2):
          l[4] = c
          for d in range(max(l)+2):
            l[5] = d
            for e in range(max(l)+2):
              l[6] = e          
              for i in range(n):
                for k in range(n):
                  if l[i] == k:
                    ans = ans + al[k]
              print(ans)
              ans = ""
            l[6] = 0
          l[5] = 0
        l[4] = 0
      l[3] = 0
    l[2] = 0
elif n == 8:
  for x in range(2):
    l[1] = x
    for a in range(max(l)+2):
      l[2] = a
      for b in range(max(l)+2):
        l[3] = b
        for c in range(max(l)+2):
          l[4] = c
          for d in range(max(l)+2):
            l[5] = d
            for e in range(max(l)+2):
              l[6] = e
              for f in range(max(l)+2):
                l[7] = f         
                for i in range(n):
                  for k in range(n):
                    if l[i] == k:
                      ans = ans + al[k]
                print(ans)
                ans = "" 
              l[7] = 0
            l[6] = 0
          l[5] = 0
        l[4] = 0
      l[3] = 0
    l[2] = 0
elif n == 9:
  for x in range(2):
    l[1] = x
    for a in range(max(l)+2):
      l[2] = a
      for b in range(max(l)+2):
        l[3] = b
        for c in range(max(l)+2):
          l[4] = c
          for d in range(max(l)+2):
            l[5] = d
            for e in range(max(l)+2):
              l[6] = e
              for f in range(max(l)+2):
                l[7] = f
                for g in range(max(l)+2):
                  l[8] = g   
                  for i in range(n):
                    for k in range(n):
                      if l[i] == k:
                        ans = ans + al[k]
                  print(ans)
                  ans = ""                          
                l[8] = 0
              l[7] = 0
            l[6] = 0
          l[5] = 0
        l[4] = 0
      l[3] = 0
    l[2] = 0
elif n == 10:
  for x in range(2):
    l[1] = x
    for a in range(max(l)+2):
      l[2] = a
      for b in range(max(l)+2):
        l[3] = b
        for c in range(max(l)+2):
          l[4] = c
          for d in range(max(l)+2):
            l[5] = d
            for e in range(max(l)+2):
              l[6] = e
              for f in range(max(l)+2):
                l[7] = f
                for g in range(max(l)+2):
                  l[8] = g
                  for h in range(max(l)+2):
                    l[9] = h         
                    for i in range(n):
                      for k in range(n):
                        if l[i] == k:
                          ans = ans + al[k]
                    print(ans)
                    ans = ""
                  l[9] = 0
                l[8] = 0
              l[7] = 0
            l[6] = 0
          l[5] = 0
        l[4] = 0
      l[3] = 0
    l[2] = 0

Submission status: Accepted

Solution code:
n=int(input())
a=[[] for _ in range(n)]
a[0]="a"
al=["a","b","c","d","e","f","g","h","i","j"]
b=[[] for _ in range(n)]
b[0]=[1]
for i in range(1,n):
    for j in range(len(a[i-1])):
        for k in range(b[i-1][j]+1):
            a[i].append(a[i-1][j]+al[k])
            if b[i-1][j]>=k+1:
                b[i].append(b[i-1][j])
            else:
                b[i].append(b[i-1][j]+1)
for i in range(len(a[n-1])):
    print(a[n-1][i])

Submission status: Accepted

Solution code:
def main():
    from collections import Counter as ct
    n = int(input())
    word_list = [""]
    for i in range(n):
        word_list2 = []
        for i in word_list:
            c = len(ct(i))
            for j in range(c+1):
                word_list2.append(i+"abcdefghij"[j])
        word_list = word_list2
    word_list.sort()
    for i in word_list:
        print(i)


main()

Submission status: Accepted

Solution code:
n = int(input())

def dfs(s, mx):
    if len(s) == n:
        print(s)
        return
    
    for c in range(ord("a"), mx+2):
        t = s
        t += chr(c)
        dfs(t, max(mx, c))

dfs("a", ord("a"))

Submission status: Accepted

Solution code:
import sys
N = int(input())

alphabets = [chr(ord('a') + x) for x in range(10)]

def dfs(S, i):
    if len(S) == N:
        yield ''.join(S)
        return
    for j in range(i):
        for w in dfs(S + [alphabets[j]], i):
            yield w
    for w in dfs(S + [alphabets[i]], i + 1):
        yield w

for w in dfs([],0):
    print(w)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

def func(remain):
    if remain == 1:
        return ['a']
    arr = [chr(ord('a') + i) for i in range(remain)]
    tmp = func(remain - 1)
    res = []
    for i in range(remain):
        res.extend(deepcopy(tmp))
        for j in range(i * len(tmp), (i + 1) * len(tmp)):
            if len(set(res[j])) < i:
                continue
            res[j] += arr[i]
    i = 0
    while i < len(res):
        if len(res[i]) < remain:
            del res[i]
        else:
            i += 1
    return res

n = INT()
ans = func(n)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
n = int(input())
L = [['a','a']]
for i in range(1,n):
    new = []
    for j in range(len(L)):
        temp = L[j][0]
        cur = ord(L[j][1])-96
        for k in range(cur+1):
            ap = temp+chr(97+k)
            if chr(97+k) < L[j][1]:
                new.append([ap, L[j][1]])
            else:
                new.append([ap, chr(97+k)])
    L = new
L.sort()
for i in range(len(L)):
    print(L[i][0])

Submission status: Accepted

Solution code:
N = int(input())
alp="abcdefghijk"

s = "a"
def dfs(s,n,alp):
  if len(s) == n:
    print(s)
  else:
    for i in range(max([alp.find(s[i]) for i in range(len(s))])+2):
      s = s + alp[i]
      dfs(s,n,alp)
      s = s[:-1] 
dfs(s,N,alp)

Submission status: Accepted

Solution code:
N = int(input())
def dfs(s):
  if len(s) == N:
    print(s)
    return
  for i in range(ord("a"), ord("z")+1):
    dfs(s+chr(i))
    if max(list(s)) == chr(i-1):
      return
dfs("a")

Submission status: Accepted

Solution code:
N = int(input())
def dfs(s):
  if len(s) == N:
    print(s)
    return
  for i in "abcdefghijklmnopqrstuvwxyz":
    dfs(s+i)
    if max(list(s)) == chr(ord(i)-1):
      return
dfs("a")

Submission status: Accepted

Solution code:
n = int(input())
ans = ['' for _ in range(n)]


def dfs(i, mx):
    if i == n:
        print(''.join(ans))
        return
    for j in range(mx+1):
        ans[i] = chr(ord('a') + j)
        dfs(i+1, max(j+1, mx))


dfs(0, 0)

Submission status: Accepted

Solution code:
n = int(input())
ans = ['' for _ in range(n)]

def dfs(i, mx):
    if i == n:
        print(''.join(ans))
        return
    for j in range(mx+1):
        ans[i] = chr(ord('a') + j)
        dfs(i+1, max(j+1, mx))

dfs(0, 0)

Submission status: Accepted

Solution code:
N = int(input())

chars = [chr(i) for i in range(ord('a'), ord('z')+1)]

ans = []

# mx: 現時点でのmax
def dfs(s, mx):
    # print(':', s, mx)
    if len(s) == N:
        # print(s)
        ans.append(s)
        return
    
    for i in range(mx + 2):
        ns = s + chars[i]
        if i == mx + 1:
            nmx = i
        else:
            nmx = mx
        dfs(ns, nmx)

dfs('a', 0)


ans.sort()
for si in ans:
    print(si)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
alpha = [chr(ord('a') + i) for i in range(26)]

def dfs(s, max_i):
  if len(s) == N:
    print(s)
  else:
    for i in range(97,max_i+1):
      dfs(s+chr(i), max(max_i, i+1))

dfs('', 97)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())

# s: 文字列
# n: これまでに使用した文字の種類数
def dfs(s:str, n:int):
    if len(s) == N:
        print(s)
        return
    
    maxc = ord("a") + n

    for c in range(ord("a"),  maxc + 1):
        dfs(s + chr(c), n+1 if (c == maxc) else n)

def main():
    dfs("", 0)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dfs(s, mx) :
    if len(s) == n :
        print(s)
        return
    else:
        for i in range(ord('a'), mx+2) :
            t = s + chr(i)
            dfs(t, max(mx, i))

n = int(input())
dfs('a', ord('a'))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
char = "".join(chr(97+i) for i in range(n))

def dfs(s, idx):
    if len(s) == n:
        print(s)
    else:
        for i in range(idx):
            dfs(s+char[i], idx if i+1 != idx else idx+1)


dfs("a", 2)

Submission status: Accepted

Solution code:
n = int(input())
char = "".join(chr(97+i) for i in range(n))


def dfs(s, idx):
    if len(s) == n:
        print(s)
    else:
        for i in range(idx):
            if i+1 != idx:
                dfs(s+char[i], idx)
            else:
                dfs(s+char[i], idx+1)


dfs("a", 2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
char = "".join(chr(97+i) for i in range(n))


def dfs(s, idx):
    if len(s) == n:
        print(s)
    else:
        for i in range(idx):
            if i+1 != idx:
                dfs(s+char[i], idx)
            else:
                dfs(s+char[i], idx+1)


dfs("a", 2)

Submission status: Accepted

Solution code:
n = int(input())
char = "".join(chr(97+i) for i in range(n))
ans = []


def dfs(s, idx):
    if len(s) == n:
        ans.append(s)
    else:
        for i in range(idx):
            if i+1 != idx:
                dfs(s+char[i], idx)
            else:
                dfs(s+char[i], idx+1)


dfs("a", 2)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
ans = []
def solve(x, n, s):
    if len(s) == n:
        ans.append(s)
        return
    for i in range(x+2):
        solve(max(x, i), n, s + chr(ord("a") + i))

def main():
    n = int(input())
    solve(0, n, "a")
    ans.sort()
    for s in ans:
        print(s)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

chars = [chr(i) for i in range(ord('a'), ord('z')+1)]

def dfs(s, mx):
    if len(s) == N:
        print(s)
    else:
        # a, b, c ..., mx
        for i in range(ord('a'), mx+1):
            ns = s + chr(i)
            if i == mx:
                nmx = i + 1
            else:
                nmx = mx

            dfs(ns, nmx)


dfs("", ord('a'))

Submission status: Accepted

Solution code:
def dfs(s,x):
    if len(s) == n:
        print(s)
    else:
        for c in range(ord('a'),ord(x) + 1):
            dfs(s + chr(c),chr(ord(x) + 1) if chr(c) == x  else x)

n = int(input())
dfs("",'a')

Submission status: Accepted

Solution code:
N = int(input())

alphabets = 'abcdefghijklmnopqrstuvwxyz'

def dfs(s, max_idx):
  if len(s) == N:
    print(s)
    return
  else:
    for i in range(0, max_idx+2, 1):
      t = s
      t = t + alphabets[i]
      dfs(t, max(i, max_idx))
    
dfs("", -1)

Submission status: Accepted

Solution code:
n=int(input())
a=1
S=[1]*n
for x in range(n):
  print(chr(S[x]+96),end="")
print()
j=1
i=1
while i<n:
  if S[-i]>max(S[:n-i]):
    i=i+1
  else:
    S[-i]+=1
    if i<=j:
      for x in range(n):
        print(chr(S[x]+96),end="")
      print()
      if S==[i for i in range(1,n+1)]:
        exit()
    else:
      j=i
      for k in range(1,i):
        S[-k]=1
      i=1
      j=1
      for x in range(n):
        print(chr(S[x]+96),end="")
      print()

Submission status: Accepted

Solution code:
def dfs(s, m):
    if len(s) == N:
        print (s)
        return
    for i in range(0, m+1):
        if i < m:
            dfs(s+chr(ord("a")+i), m)
        else:
            dfs(s+chr(ord("a")+i), m+1)

N = int(input())
dfs("", 0)

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())
a_num = ord("a")
deque = deque()
deque.append(("a", a_num))
ans = []

if n > 1:
    while len(deque) > 0:
        s, s_num = deque.popleft()
        for i in range(a_num, s_num + 2):
            s_nxt = s + chr(i)
            s_num = max(s_num, i)
            if len(s_nxt) == n:
                print(s_nxt)
            else:
                deque.append((s_nxt, s_num))
else:
    print("a")

Submission status: Accepted

Solution code:
# D - String Equivalence 
def dfs(s, mx):
    if len(s)==n:
        print(s)
        return
    for c in range(ord('a'), ord(mx)+1):
        dfs(s+chr(c), (chr(ord(mx)+1) if ord(mx)==c else mx))

n=int(input())
dfs('','a')

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())
a_num = ord("a")
deque = deque()
deque.append(("a", a_num))
ans = []

if n > 1:
    while len(deque) > 0:
        s, s_num = deque.popleft()
        for i in range(a_num, s_num + 2):
            s_nxt = s + chr(i)
            s_num = max(s_num, i)
            if len(s_nxt) == n:
                ans.append(s_nxt)
            else:
                deque.appendleft((s_nxt, s_num))

    ans.sort()
    print(" ".join(ans))

else:
    print("a")

Submission status: Accepted

Solution code:
# D - String Equivalence 
def dfs(s,m):
    if len(s) == n:
        print(s)
        return 0
    for i in range(m + 1):
        if i < m:
            dfs(s+chr(ord('a')+i),m)
        else:
            dfs(s+chr(ord('a')+i),m+1)

n=int(input())
dfs('', 0)

Submission status: Accepted

Solution code:
import collections

def bfs(N):
    S = "abcdefghij"
    result = []
    deq = collections.deque(["a"])

    while deq:
        s = deq.popleft()
        if len(s) == N:
            result.append(s)
            continue
        else:
            for i in S[:len(set(s))+1]:
                deq.append(s + i)
    return result

N = int(input())
ans = bfs(N)
print('\n'.join(ans))

Submission status: Accepted

Solution code:
import collections
N = int(input())

S = "abcdefghij"
result = []
deq = collections.deque(["a"])

while deq:
    s = deq.popleft()
    if len(s) == N:
        result.append(s)
        continue
    else:
        for i in S[:len(set(s))+1]:
            deq.append(s + i)

print('\n'.join(result))

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n=int(input())
al=[chr(ord('a') + i) for i in range(26)]
d=deque([])
d.append([0])
# print(d)
while 1:
    if len(d[0])==n:
        break
    tmp=d.popleft()
    for i in range(max(tmp)+2):
        d.append(tmp+[i])
    
d=list(d)
d.sort()
for i in range(len(d)):
    tmp=""
    for j in range(len(d[0])):
        tmp+=al[d[i][j]]
    print(tmp)

Submission status: Accepted

Solution code:
# DFS(再帰関数)による全探索
# AC:  msec(Python3)
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def dfs(s, N):
    """
    param s:今の文字列
    param N:文字列の長さ

    """
    S = "abcdefghij"

    if len(s) == N:
        print(s)
    else:
        for c in S[:len(set(s))+1]:
            dfs(s + c, N)


def main():
    N = int(readline())

    dfs("", N)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

lst = []
m = 0
temp = [[0]]

while temp:
    p = temp.pop()
    if len(p)==N:
        lst.append(p)
    else:
        for i in range(max(p)+2):
            s = p[:]
            s.append(i)
            temp.append(s)

lst.sort()
abc = 'abcdefghij'
for l in lst:
    print(*[abc[i] for i in l], sep='')

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
# 97: a
q = deque([["a", 97, 1]])
while q:
    s, num, count = q.pop()
    if count<n:
        for i in range(num+1, 96, -1):
            q.append([s+chr(i), max(num, i), count+1])
    else:
        print(s)

Submission status: Accepted

Solution code:
n = int(input())
D = {}
a ,b , c, d, e, f, g, h, i, j = 'a','b','c','d','e','f','g','h','i','j'
D[10] = [a,b,c,d,e,f,g,h,i,j]

def output(str_n1):
    num = len(set(str_n1))
    return D[10][0:num+1]

def plus1(moji):
    b = []
    for i in moji:
        d = output(i)
        # print(i)
        for j in d:
            a = []
            a.extend(i)
            a.append(j)
            b.append(a)
    return b

s = 'a'
dic = {}
dic[0] = s
for i in range(10):
    dic[i+1] = plus1(dic[i])

for j in dic[n-1]:
    print(''.join(j))

Submission status: Accepted

Solution code:
# 幅優先探索による全探索
from collections import deque
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def bfs(N):
    """
    param N:文字列の長さ

    """
    S = "abcdefghij"
    result = []
    queue = deque(["a"])
    
    while queue:
        s = queue.popleft()
        if len(s) == N:
            result.append(s)
            continue
        else:
            for i in S[:len(set(s))+1]:
                queue.append(s + i)
    
    return result


def main():
    N = int(readline())

    ans = bfs(N)
    print("\n".join(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 幅優先探索による全探索
from collections import deque
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def bfs(N):
    """
    param N:文字列の長さ

    """
    S = "abcdefghij"
    result = []
    queue = deque(["a"])
    
    while queue:
        s = queue.popleft()
        if len(s) == N:
            result.append(s + "\n")
            continue
        else:
            for i in S[:len(set(s))+1]:
                queue.append(s + i)
    
    return result


def main():
    N = int(readline())

    ans = bfs(N)
    print("".join(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
l = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
ans = []
def dfs(s, mx):
    if len(s) == N:
        ans.append(s)
        return
    for i in range(mx+1):
        # 新しい文字を登場させる
        if i == mx:
            # print("a:", s+l[i])
            dfs(s+l[i], mx+1)
        else:
            # print("b:", s+l[i])
            dfs(s+l[i], mx)


dfs("", 0)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
# 深さ優先探索による全探索
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def dfs(N):
    """
    param N:文字列の長さ

    """
    S = "abcdefghij"
    result = []
    stack = ["a"]
    
    while stack:
        s = stack.pop()
        if len(s) == N:
            result.append(s)
            continue
        else:
            for i in S[:len(set(s))+1]:
                stack.append(s + i)
    
    return result


def main():
    N = int(readline())

    ans = dfs(N)
    print("\n".join(ans[::-1]))
            

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

cset = [chr(ord('a')+i) for i in range(N)]
sset = ['a'] * N
def rec(di, usedci):
    if di >= len(sset):
        print(''.join(sset))
        return
    for i in range(usedci+1):
        sset[di] = cset[i]
        rec(di+1, usedci)
    sset[di] = cset[usedci+1]
    rec(di+1, usedci+1)

rec(1, 0)

Submission status: Accepted

Solution code:
N = int(input())
ASC = 97

def dfs(s, mx):
    if len(s) == N:
        print(s)
        return
    for c in range(ASC, mx+2):
        t = s + chr(c)
        dfs(t, max(mx, c))
    
s = 'a'
mx = ord(s)
dfs(s, mx)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def dfs(N):
    """
    param N:文字列の長さ

    """
    result = []
    stack = [("a", 1)]
    
    while stack:
        s, max_ = stack.pop()
        if len(s) == N:
            result.append(s)
            continue
        else:
            for i in range(max_+1):
                stack.append((s + chr(97+i), max(max_, i+1)))
    
    return result


def main():
    N = int(readline())

    ans = dfs(N)
    print("\n".join(ans[::-1]))
            

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


s = 'abcdefghijklmnop'
N = I()


def f(n, seq, m):
    for i in range(m + 1):
        if n == N:
            print(seq + s[i])
        else:
            f(n + 1, seq + s[i], max(m, i + 1))


f(1, '', 0)

Submission status: Accepted

Solution code:
n = int(input())

def dfs(s):
  if len(s) == n:
    print(s)
  else:
    for i in range(ord(max(s)) - ord('a') + 2):
      dfs(s + chr(i + ord('a')))
      
s = 'a'
dfs(s)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


def dfs(s):
    if len(s) == n:
        print(s)
        return
    kind = len(set(s))
    for i in range(kind + 1):
        dfs(s + chr(ord('a') + i))


n = int(input())
dfs('')

Submission status: Accepted

Solution code:
n = int(input())


def dfs(s, m):
    if len(s) == n:
        print(s)
        return 0
    for i in range(m + 1):
        if i < m:
            dfs(s + chr(ord('a') + i), m)
        else:
            dfs(s + chr(ord('a') + i), m + 1)


dfs('', 0)

Submission status: Accepted

Solution code:
N = int(input())

dic={0:'a',1:'b',2:'c',3:'d',4:'e',5:'f',6:'g',7:'h',8:'i',9:'j'} #標準形の文字列は同型の文字列の中で辞書順最小であることから、新たに付け加えるべき文字は順にa,b,c...となる
ans=[['a',1]]
for i in range(1, N):
 tmp=[]
 for prev,val in ans:
   for j in range(val+1): #(今見ている文字列に使われている文字の種類数+1)種類の文字を付け加える
     if j!=val: #今見ている文字列に使われている文字を付け加えるとき、文字の種類数は増加しない
       tmp.append([prev+dic[j],val])
     else: #今見ている文字列に使われていない文字を付け加えるとき、文字の種類数が増加する
       tmp.append([prev+dic[j],val+1])
 ans=tmp
ans=sorted(ans,key=lambda x:x[0]) #生成した標準形の文字列を辞書順昇順に並べ替える
for i in range(len(ans)):
 print(ans[i][0])

Submission status: Accepted

Solution code:
from sys import stdin


def dfs(str, mx):
    if len(str) == N:
        print(str)
        return

    for i in range(ord("a"), mx+2):
        # print(i,mx+2)
        if i > mx:
            mx = i
        t = str
        t = t+chr(i)
        # print(str)
        dfs(t, mx)
    # print(str)


# S = stdin.readline().rstrip().split()
N = [int(x) for x in stdin.readline().rstrip().split()][0]


dfs("", ord("a")-1)

Submission status: Accepted

Solution code:
#python3
n = int(input())

def dfs(s):
    if len(s) == n:
        print(s)
        return
    else:
        kind = len(set(s))
        for i in range(kind+1):   
            t = s
            t += chr(ord('a') + i)
            dfs(t)
def main():
    dfs('a')
main()

Submission status: Accepted

Solution code:
N = int(input())

def dfs(x, n):
    if len(x) == n:
        s = "".join(chr(ord("a")+x[i]) for i in range(n))
        print(s)
    else:
        # 下桁に近づくにつれて文字の種類が増えるように再帰させる
        for i in range(max(x)+2):
            dfs(x+[i], n)

dfs([0], N)

Submission status: Accepted

Solution code:
n = int(input())

def dfs(s, mx):
    if len(s) == n:
        print(s)
        return
    else:
        for i in range(ord("a"), ord(mx)+2):
            t = s
            t += chr(i)
            dfs(t, max(chr(i), mx))

dfs("a", chr(ord("a")))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)
n = int(input())


def dfs(s, max_c):
    if len(s) == n:
        print(s)
        return
    for i in range(ord("a"), max_c+2):
        t = s
        c = chr(i)
        t += c
        dfs(t, max(max_c, i))

dfs("", ord("a")-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    ABC = ("a", "b", "c", "d", "e", "f", "g", "h", "i", "j")

    def dfs(s, n, i):
        if n == N:
            print(s)
            return
        for j in range(i+1):
            dfs(s + ABC[j], n+1, i + 1 if i == j else i)
    dfs("a", 1, 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
li="abcdefghijklmn"
n=int(input())
def f(s,l,k):
    global li,n
    if l==n:print(s);return
    for i in range(2+k):
        f(s+li[i],l+1,max(i,k))


f("a",1,0)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    
    def dfs(s, mx):
        if len(s) == N:
            print(s)
        else:
            for i in range(ord('a'), ord(mx)+1):
                m = ord(mx)+1 if i == ord(mx) else ord(mx)
                dfs(s + chr(i), chr(m))
    dfs('', 'a')

solve()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n = int(input())
  def dfs(s, mx):
    if len(s) == n:
      print(s)
      return
    for c in range(ord('a'), ord(mx)+1):
      dfs(s + chr(c), (chr(ord(mx) + 1) if ord(mx) == c else mx))
  dfs('', 'a')
      
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
al=[chr(ord('a') + i) for i in range(26)]
norm=defaultdict(list)
def max_al(s):
  tmp=0
  for i in range(len(s)):
    tmp2=al.index(s[i])
    tmp=max(tmp,tmp2)
  return tmp

for i in range(11):
  if i==0:
    norm[1]=['a']
  else:
    for char in norm[i-1]:
      range_digit=max_al(char)+2
      for s in al[0:range_digit]:
        norm[i].append(char+s)

for char in norm[n]:
  print(char)