GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
1.2k views

How many sub strings of different lengths (non-zero) can be found formed from a character string of length $n$?

  1. $n$
  2. $n^2$
  3. $2^n$
  4. $\frac{n(n+1)}{2}$

 

asked in Combinatory by Veteran (66.1k points) 1148 2197 2522
retagged by | 1.2k views
Anyone please confirm ans ... I am getting option A (n) as correct answer as question is asking for different length substrings.

Aswer will be D  (asuming all characters in string are distinct)

Take an example String "abc"

Substrings of length 1 = {a,b,c}

Substrings of length 2 = {ab,bc}

Substrings of length 3 = {abc}

Total Substrings of non zero length will be 3+2+1 = 6

However Answer will be A, if all characters are same

consider "aaa"

Substrings of length 1 = {a}

Substrings of length 2 = {aa}

Substrings of length 3 = {aaa}

So answer can be vary from n to $\frac{n(n+1)}{2}$ if the distinct keyword is not given!!

^ what do you mean by - strings of different lengths (non-zero)  ??

^

strings of different lengths (non-zero) 

means some string are of length 1

Some string lengh 2

................some string length n

 

it doesnot mean each string of different length

Okay, thanks:)
why is substring different from subsets?

2 Answers

+13 votes
Best answer
assuming an string of length n provided all alphabets are distinct..

no of strings of length 1 = n

no of strings of length 2 = n-1

no of strings of length 3 = n-2
.
.
.
no of string of length n = 1
total = n + (n -1) + (n - 2) + (n - 2) + ..... + 1
         = n(n+1)/2
answered by Veteran (48k points) 39 162 393
selected by

Lemme know what they actually mean by "different length"? ..according to your answer you are assuming like

# total strings of length1+ # total strings of length2 ...+ #total strings of length n ....

But there are n strings of length 1 (same langth) ,n-1 of length 2 (same length) ....1 string of length n ...so answer can be 'n' in that way...

So what they actually mean..

Let string be {a,b,c}

subs of length 2 are ab,bc,ac .how is it then following no of strings of length 2 = n-1.plz clarify

@Digvijay

@Gate Mm

if abc is a string, then length 2 sub-strings will be ab,bc only.
Because substring is the part of string. So ...ac.... is not part of the string.
How to know if all alphabets are distinct? If they are same then we have the option (a) as the answer
0 votes

The correct answer is (D) n⨉(n+1)/2

answered by Boss (8.8k points) 3 8 12
and y ???


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23242 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7096 Points

  4. srestha

    6012 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4928 Points

  7. Sachin Mittal 1

    4762 Points

  8. joshi_nitish

    4278 Points

  9. sushmita

    3954 Points

  10. Rishi yadav

    3744 Points


Recent Badges

Popular Question Ml_Nlp
Notable Question set2018
Notable Question rahul sharma 5
Notable Question Sanjay Sharma
Notable Question Lakshman Patel RJIT
Popular Question makhdoom ghaya
Popular Question Çșȇ ʛấẗẻ
Reader kenzou
Popular Question mystylecse
Notable Question Sanjay Sharma
27,262 questions
35,076 answers
83,760 comments
33,185 users