FilesExpand file tree

 main

/

google1.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

49 lines (41 loc) · 980 Bytes

 main

/

google1.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

49 lines (41 loc) · 980 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

//Find the number of non-overlapping palindromic triplet substrings of a string. Note: These triplets when combined may or mayn't be equal to the length of the string

//Example: abbccd => a,b,d is also possible {a,b,d are 3 palindromic substrings,they are non overlapping}

int ispal(int lo,int hi,string s)

{

while(lo<hi)

{

if(s[lo]!=s[hi])

return 0;

lo++;

hi--;

}

return 1;

}

vector<string>temp;

int google=0;

void rec(int i,int j,string s)

{

if(i >j )

{

return;

}

for(int k=i;k<=j;k++)

{

if(ispal(i,k,s))

{

temp.push_back(s.substr(i,k-i+1));

if(temp.size()==3)

google++;

rec(k+1,j,s);

temp.pop_back();

}

}

}

class Solution {

public:

long long partition(string s) {

google =0;

rec(0,s.size()-1,s);

return google;

}

};