5
\$\begingroup\$

Problem Statement: https://www.hackerrank.com/challenges/similar-strings

enter image description hereenter image description here


I got the logic correct. However it times out for testcase 8 onwards

I would like some suggestions on optimizing this code

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;


public class SimilarStrings {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();

        // number of queries
        int queries = Integer.parseInt(line.split(" ")[1]);
        // data string
        String string = in.nextLine();
        // query lines
        List<String> lines = new ArrayList<>();
        for (int i = 0; i < queries; i++) {
            lines.add(in.nextLine());
        }
        lines.stream().map(query -> solve(query, string))
                .collect(Collectors.toList())
                .stream()
                .forEach(System.out::println);
    }

    private static int solve(String query, String string) {
        String queryStrArr[] = query.split(" ");
        int start = Integer.parseInt(queryStrArr[0]);
        int end = Integer.parseInt(queryStrArr[1]);
        // special case
        if (end == start) {
            return string.length();
        }
        String mainSubstring = string.substring(start - 1, end);
        List<String> substrings = getOtherSubStrings(string, start, end);
        // +1 for self
        return (int) substrings.parallelStream()
            .filter(substring -> equals(mainSubstring, substring))
            .count() + 1;       
    }

    private static boolean equals(String string1, String string2) {
        char[] arr1 = string1.toCharArray();
        char[] arr2 = string2.toCharArray();

        for (int i = 0; i < string1.length(); i++) {
            for (int j = i + 1; j < string1.length(); j++) {
                if (arr1[i] == arr1[j]) {
                    if (arr2[i] != arr2[j]) {
                        return false;
                    }
                } else if (arr2[i] == arr2[j]) {
                    return false;
                }
            }
        }
        return true;
    }

    private static List<String> getOtherSubStrings(String string, int start, int end) {
        int length = end - start + 1;
        List<String> lines = new ArrayList<>(string.length());
        for (int i = 0; i <= string.length() - length; i++) {
            if (i == start - 1) {
                continue;
            }
            lines.add(string.substring(i, i + length));
        }
        return lines;
    }
   }

Dataset for which it times out:

3000 3000
jhhjfiijiacacgcghejcedeaehehbhbbbcjdcdeeebbaieiebaicfedhdbebibjjiaifahaaahjhagafgfegjhbebijihhbhihahigdfjfbgfdfjbejgahfdgdifgbgegjjcjchjbiaiagjagagejajdafjcddbjfjiiebiaagigiefhahhhcchcegjfgggfedidgbdgfdcfggifdfdgbgcgfbfbijajhcbjdbdedecgigcabijgjdfabggfgfagcdjdjhgjhjhbgjgijegbhgehhhebidihccfigiefedeaadhdchghhhgaghjhcjcfjagefedadggegdghgdjibibfcdecihedbdgbhcdceaefgchcjgjhihgbgbgigihhjaeihidehchbhhggaeajbjchchccccacceeeceeiejcaiedeijfhgaghbjbjjgjgdbcbjdhhdcachbabcdjifdfjgcieicececbbbibgafjghghigjheafdhdhfjcdghgiejchhehejhfigigahgagachghdgbheddfhbhiicfiggaiaicbjgjjjeejecahbaaabcdidafdabdebaaibdbdafaeabfbfihghjefhdfdcdcecdaiaihjjhbiihigegeaeajchecdcgcjcjfjfffehdedcccffgicicfgbjbjgfabfifhfgfgegeeebaibifffeehdfdfehdbcfigiefedeaadhdcjagajhjehebhgacbcdgdaacadajadhififbedceijcdfdafjedecgcbaejehhejejajhhhhjhedhhjddhdgbgjgggjhjgagbabcahjfcfihigjiadedecbifbdgfieijegbibfhfcjbgbaabgbgjgaaaagabiaagiiaihchghhhgaghjhcjcfjagefedadgghbcjgjhihgbgbgigihicecjfjdaddjffafhhhbgfgcggcdcacejcicaefajhgcijidcjejfjjaagcghfhejejeeeegeeccceccichegicdcihbjagajfhfhhaheejeaaachehfhhfifjfbgfdfjbejgahfdgdijeaaachehfhhfifjfbgfdfjbejgahfdgdifgbgeggjjhfhaeabgbgbbbbhbbfffbffdfabhdfifdacgjhjgeaeaajajiebeaiggibhbgehebiadcicajbdfdbfbfbeeedejhcajgjgdjagfhcigigcabijgjdfabggfgfagcdjdjhgjhjhbgjgijegfiicgegddbcdjjhdhdbeajaaaffafbhgehhhebidihciheifehhdeieihchfhececdgjgafcgicibibfbihdhdgaageddgdjfjfhfhabgfbibjbabacacccfgifibbbccjdbdbcjdfebiaicbcdcggdjdejajjjagajhjehebhgacbcdgdaacadajadhififbedceijcdfdafjedecgcbaejehahjijafafaiaijiecehbhdgddhbbgbjjjfabaeaaedegecheiegcbghjaeihidehchbhhggaeajbjchchccccacceeeceeiejcaiedeijfhgaghbjbjjgjgdbcbjdhhdcachbabcdjifdfjfgcgihjiegigeejeaeijhghghdabdbgbcicacachchbfgcggcdcacejcicaefajhgcijidcjejfjjaagcghfhejejeeeegeeccceccichegicdcihbjagajfhfhhahadfefhdjjdegejfgfedhibdbhaeiciececefffifagbhajajiahjcgbdjdjbhedajaichejjcjchjbiaiagjagagejajdafjcddbjfjiiebiaagigiefhahhhcchcegjfgggfedidgbdgfdcfggifdfdgbgcgfbfbijajhcbjdbdedecedgigijhhjfiijiacacgcghejcedeaehehbhbbbcjdcdeeebbaieiebafhfhabgfbibjbabacacccfgifibbbccjdbdbcjdfebiaicbcdcggdjdehgaghjhcjcfjagefedadggegdghgdjibibfcdecihedbdgbhcdceaefgchcjjchchghjjjjhjcdjjhddjdafahaaahjhagafgfegjhbebijihhbhihahigdcdcefibfdabicihcdbgbcicacacfghgadahchchdhdadfbfgegijiigeejeaaachehfhhfifjfbgfdfjbejgahfdgdifgbgeggjjhfhaeabgbgbbbbhbbfffbffdfabhdfifdacgjhjgeaeaajabbgbjjjfabaeaaedegecheiegcbghjaeihidehchbhhggaeajbjchchccccacceeeceeiejcaiedeijfhgaghbjbjjgjgdbcbjdhhdcachbabcdjifdfjgcieicececbbbibgafjghghigjheafdhdhfjcdghgiejchhehejhfigigahgagachghdgbheddfhbhiicfiggaiaicbjgjjjeejecahbaaabcdidafdabdebaaibdbdafaeabfbfihghjefhdfdcdcecdaiaihjjhbiihigegeaeajchecdcgcjcjfjfffehdedcccffgicicfgiebcdjdfcfifhhigibgjgggjhjgagbabcahjfcfihijjfjijgjiadedecbifbdgfieijegbibfhfcjbgbajagdgjejejdjdgdbfbacaihiiacchcgggejcjbjjbibhbfabdbhfchagjbdadibafacaahhjbjgcgfafaffffjffbbbfbbdbgfjdbibdgeahjhacgcgghghicfcgiaaifjfacjcfigdeiegehfhdagdbhdhbbgbjbdgahahaijcichcfdfjfjfafacgebabafaaijfjajafjfhfhfcfajdgfafahaggggagfiggaiiiicciiieiegbccddbdadhdadfaiafifhffhbgdjficidgaha
1 138
1 813
1 831
1 843
1 848
1 1020
1 1028
1 1165
1 1242
1 1525
1 1741
1 1751
1 1848
1 1985
1 1990
1 2015
1 2046
1 2129
1 2217
1 2312
1 2428
3 706
3 1348
4 36
4 814
7 321
8 1263
9 1237
9 1747
9 1995
10 1321
10 1331
12 193
12 713
12 1420
13 268
13 888
13 1069
13 2119
14 1346
15 79
15 601
18 1253
19 1119
19 2834
23 591
24 34
24 711
25 300
25 2168
26 267
26 645
26 646
27 718
28 636
28 825
29 67
29 360
31 757
33 2279
35 879
36 2024
42 1726
44 782
45 66
48 71
48 147
48 297
48 568
48 890
48 1372
49 998
51 1492
52 855
54 1093
54 1374
55 682
56 261
56 1101
57 913
57 1491
58 976
59 673
60 432
60 811
60 1219
60 1404
60 1492
61 1421
62 263
62 546
63 84
63 186
63 875
63 990
66 103
66 1522
66 2270
67 1244
67 2763
68 98
69 291
70 533
72 472
72 1265
74 1897
75 2574
76 151
76 157
76 342
78 217
78 224
78 578
81 366
82 479
82 901
83 986
84 450
86 129
86 1175
88 569
89 407
90 919
91 992
92 2123
93 1471
94 1927
96 361
98 235
98 330
99 271
99 303
100 176
100 499
101 1533
101 2044
102 521
103 2865
104 117
105 399
105 904
106 899
109 910
109 1340
109 2622
110 1239
112 849
114 397
114 1239
116 447
119 1313
120 125
120 621
120 2066
121 553
122 1185
122 1991
123 1007
123 1959
124 1539
125 393
125 952
126 1006
127 1701
128 517
128 527
128 2582
129 971
130 250
131 508
131 1785
133 685
133 780
134 1411
135 640
135 982
136 1114
137 316
139 611
140 1208
140 1374
141 786
144 843
144 861
145 437
146 463
148 925
149 563
150 458
150 876
151 1181
151 1368
152 1534
153 211
153 574
154 860
155 1452
155 2014
156 171
157 614
158 852
158 1737
159 522
160 1295
160 2546
161 456
161 1152
162 2564
163 516
164 659
165 1506
167 786
168 257
168 1786
168 2102
168 2325
168 2527
169 286
169 1102
173 231
174 2233
175 1025
176 1481
177 1382
179 218
179 429
179 1186
179 1560
181 662
183 365
183 1146
183 1326
184 483
185 211
185 730
185 1552
186 864
187 2337
188 1481
189 200
191 237
192 362
192 688
193 1389
193 1517
193 2516
194 197
194 551
194 688
194 954
194 1493
196 945
196 1464
196 2803
197 980
197 1209
199 1011
200 575
202 1480
204 463
204 1457
204 1477
205 977
206 420
207 325
207 1383
207 1518
208 953
209 752
210 233
211 1350
211 1422
212 317
212 483
212 1540
213 358
213 2940
214 261
214 916
214 1076
217 2532
218 803
218 877
220 993
221 765
221 1117
227 491
228 1229
230 360
230 1424
231 370
235 379
235 1402
236 280
236 368
236 620
236 1074
237 1010
237 1246
237 1613
238 828
239 712
240 1284
241 521
242 292
243 1872
246 333
247 425
248 873
249 1617
250 1207
251 332
251 1462
255 358
255 534
255 1419
256 1090
257 683
257 974
257 2176
258 1312
258 2997
259 509
260 1041
261 310
262 1376
264 1167
265 324
265 1268
266 2113
267 2820
268 508
268 639
268 1020
269 359
269 366
269 485
269 1483
270 1119
270 1517
271 1318
272 578
273 1541
273 1550
273 2328
274 1545
275 804
276 832
277 1561
278 2416
280 582
281 429
281 722
281 793
282 393
282 944
285 761
285 847
287 1024
288 883
288 1292
288 1471
289 1966
291 1423
293 887
294 811
294 1180
294 2045
295 733
295 1291
295 1355
297 878
297 1641
298 399
298 873
298 1749
300 646
301 348
301 447
302 810
304 450
304 966
304 1240
306 1044
307 561
307 1234
307 1417
309 2017
310 357
310 665
313 782
315 517
315 1125
316 612
316 875
316 1952
317 553
318 524
321 512
322 383
323 731
323 864
323 1878
324 1082
326 525
326 746
326 1730
327 418
327 554
327 1111
328 436
328 916
329 1540
331 751
332 360
333 1092
334 2479
335 1489
338 575
339 349
339 1558
341 407
341 492
341 739
341 1653
343 355
343 1636
344 562
344 694
346 1410
347 1421
349 640
350 475
350 1185
350 1595
350 1816
352 729
355 604
357 1560
361 1591
365 610
366 1226
366 1345
366 1356
367 2499
368 410
368 606
368 930
369 435
371 887
372 493
372 1067
373 411
373 675
373 744
373 859
373 1625
373 1675
373 2721
375 667
375 1658
376 600
377 451
378 1157
379 754
380 808
381 1478
384 1354
384 2028
385 598
386 2755
390 1677
390 2743
391 565
391 1829
393 1162
393 1530
395 535
396 503
396 1256
397 2839
399 1629
400 456
401 2667
403 689
403 697
404 772
404 1148
404 1393
405 759
407 764
407 1176
408 1043
410 1764
411 1013
414 1583
417 1537
418 457
418 1470
419 1118
419 1437
420 1321
421 1309
424 2785
425 1541
426 468
427 649
428 526
428 1553
430 701
430 786
432 780
432 1619
433 560
433 1665
435 444
436 766
436 1210
437 1126
438 1304
439 963
439 1475
440 515
440 834
441 442
441 516
441 1052
441 1486
444 445
444 494
444 656
445 714
445 860
446 726
446 1514
447 1311
448 493
449 600
450 1352
451 790
451 1352
451 2254
452 654
454 1511
455 1354
455 1658
456 521
456 1081
456 1773
456 2041
457 525
458 883
458 2670
459 1313
460 875
460 2763
461 862
461 919
461 990
461 2920
462 569
462 659
462 1588
464 477
464 644
464 762
464 1472
465 1118
465 1645
466 1675
467 726
467 965
467 1072
467 2928
468 641
468 925
468 1262
469 842
470 1828
474 542
475 602
475 845
476 604
477 485
477 663
477 785
477 2978
478 662
479 647
479 932
480 488
480 706
482 595
482 636
483 1753
484 693
485 620
485 1116
485 1178
486 737
486 867
488 1054
489 1091
490 857
491 1130
493 573
493 884
494 742
495 627
495 1031
496 1290
497 1000
497 1736
498 736
498 1278
500 872
501 938
501 955
504 624
505 1103
507 1039
508 1158
508 1557
508 1717
509 710
509 1462
510 926
510 1464
511 1346
512 849
512 1789
513 657
513 1259
514 678
514 1114
515 1988
517 671
517 1254
519 617
519 702
519 958
519 1265
520 633
521 964
523 879
523 1262
523 1475
523 1496
524 861
524 966
526 1578
527 929
529 785
530 733
530 1390
531 680
532 771
534 1509
536 2077
538 617
538 1186
539 985
540 709
540 1241
541 719
541 2897
544 2861
545 724
547 585
547 726
547 1284
548 1088
549 1797
551 641
551 1058
551 2299
552 2743
553 613
553 796
553 2770
554 576
555 724
555 791
555 1136
556 609
556 611
557 898
557 1528
558 731
560 1689
561 613
561 705
562 1656
563 822
563 2240
564 767
564 1151
565 1488
567 1327
567 2782
568 823
568 1098
568 2614
570 586
570 983
571 662
572 1403
572 1661
573 650
575 633
575 761
575 1385
576 1376
577 593
577 791
578 804
579 1079
580 2154
581 651
581 1248
582 883
583 886
584 1052
586 922
586 1659
586 2866
587 1141
589 615
590 2375
592 904
592 1448
593 1580
593 1695
596 1063
597 2344
598 1544
599 620
599 709
600 2315
601 950
601 1211
603 758
603 849
604 622
606 1456
606 2420
607 745
607 1174
607 1348
608 2115
610 1805
611 1121
611 1216
612 994
613 958
613 1764
614 1434
614 2563
615 1162
615 1448
620 741
620 1057
620 1651
621 843
621 1441
621 2283
622 833
622 2917
624 688
624 691
624 1505
625 830
625 1070
626 675
626 1376
627 671
627 978
628 1716
629 999
630 1047
630 1546
631 699
632 1708
633 1613
633 1685
633 2932
634 948
634 2480
636 651
636 1426
637 1811
638 898
638 974
639 1536
640 1033
640 1663
643 1271
644 1146
645 987
646 1019
646 1749
647 2327
648 816
648 908
648 1191
648 1555
648 2033
649 766
649 1445
650 840
650 1336
650 2542
651 1065
651 1468
653 895
654 1586
655 775
655 1136
655 1182
655 1448
656 775
656 1126
657 702
657 908
657 1592
657 2794
658 802
658 906
660 795
660 1067
660 1556
661 1198
663 728
663 1056
663 2871
664 722
664 1785
665 1407
666 1074
667 2434
668 684
668 903
669 1156
669 1184
670 1259
671 883
671 1006
671 1612
671 2539
672 939
672 1108
674 2041
677 1251
677 1455
678 759
678 842
678 1460
679 943
679 1412
679 1507
680 993
680 1377
681 1289
681 1570
682 770
684 1226
685 764
685 1537
686 1403
687 1471
688 1250
689 831
689 1273
691 845
691 1228
691 1319
692 1182
693 757
693 1215
693 1349
694 1816
697 1717
698 1014
700 1172
700 1787
703 1090
703 1322
703 2707
704 1037
704 1764
706 758
706 2371
707 774
708 1032
708 1187
709 773
709 832
709 1054
709 1634
710 1024
710 1266
711 991
712 799
713 1263
713 2198
714 1311
714 1654
716 1691
716 2240
716 2799
717 1215
717 1408
719 1187
719 1680
719 1788
721 1133
722 1204
722 1355
722 1666
722 1670
723 2221
724 2906
727 1034
727 1369
727 1441
730 1385
730 1440
732 748
732 1383
733 838
734 1158
734 1742
737 757
737 1650
739 1222
741 938
743 981
743 1456
743 1463
745 853
745 1364
746 1761
747 999
748 1484
749 857
749 961
749 1810
750 831
750 1281
750 2436
751 1283
751 1432
752 1334
753 847
757 787
758 930
758 1215
758 2182
759 1642
759 1693
759 1727
761 1198
761 1609
762 1306
763 1268
766 768
766 1336
767 1639
767 2152
768 1159
768 1589
769 902
770 1445
770 1682
771 815
771 1488
772 900
772 1065
772 1776
774 1334
775 1461
775 2327
778 1127
778 1868
780 919
780 1135
782 876
782 1183
784 1437
784 1756
785 930
785 1267
785 1856
785 2469
786 786
786 1301
787 1523
788 1404
790 883
790 1249
790 1364
790 1980
791 1438
793 890
793 986
793 1107
794 1475
794 2327
795 1123
796 1150
796 1298
796 1640
797 1307
797 1662
798 938
798 1041
800 877
800 1205
801 1187
801 1537
802 807
802 1527
803 2541
804 1005
805 1589
805 1839
806 843
806 1313
807 825
807 1064
807 1189
807 1207
807 2579
809 1363
809 1457
810 2657
812 1274
812 1313
813 1045
815 851
816 960
818 1096
818 1577
819 984
821 1084
824 1001
825 1122
826 877
826 1177
826 1187
827 2180
828 2726
829 1070
830 1578
831 1475
832 1407
833 1071
833 1282
833 1500
835 1070
836 1195
836 1952
837 1178
838 1435
839 2552
839 2793
840 1016
840 1503
842 910
843 1745
844 988
844 1067
844 1142
844 1308
845 1631
846 1507
847 1796
849 1380
849 1650
851 1698
852 1306
852 1538
855 859
855 1230
858 972
858 1796
859 1509
860 1106
861 990
863 878
863 1592
863 1642
864 1237
864 2925
865 1582
867 1061
867 1374
867 1403
868 1282
868 1328
869 1518
870 1362
871 1516
872 953
872 1397
872 2649
873 1271
873 1273
875 903
876 1284
877 935
877 1739
880 1533
881 1043
881 1220
881 1516
882 1325
883 1863
884 1244
885 2154
886 926
886 1294
886 1486
886 1596
886 1848
890 1297
891 1436
891 1503
892 1422
892 1717
893 1140
893 1282
893 1339
894 1631
896 1700
896 2727
898 1023
898 1450
899 2698
900 1178
900 1184
900 1460
900 1729
902 944
904 1543
904 2951
905 1927
907 2224
908 1226
908 1557
909 2231
909 2232
910 2529
911 1257
911 1663
911 1762
912 1444
912 1814
912 2915
914 1291
914 1555
914 1860
915 1109
916 976
916 2303
917 1346
918 1480
919 1419
920 1809
921 1637
921 1822
922 1267
923 1280
923 1746
923 2931
924 2660
926 1349
926 1707
927 998
927 1207
928 1085
930 1026
931 1292
931 1489
931 1741
932 1264
933 1477
934 969
935 1705
936 1513
940 1575
940 1676
941 1461
942 1620
942 1949
943 1150
944 1069
944 1218
944 1843
947 1076
947 1109
947 1154
947 1605
948 1450
949 1100
949 1127
950 1733
951 1215
951 1826
951 2168
952 1441
953 1357
953 1462
955 1390
955 1639
955 1956
956 967
957 1243
957 1961
960 1281
960 1859
961 1559
961 1746
962 1202
962 1262
962 1586
963 1128
963 1485
964 1033
964 1252
966 1366
966 1765
966 2569
966 2995
967 1248
967 2644
969 1545
970 1305
972 1650
972 1723
973 1657
975 1378
975 1979
976 1191
976 1217
978 1362
978 1423
978 1858
979 1606
979 2436
980 1420
980 1465
980 1853
983 1493
983 1573
984 1790
985 1541
987 1134
988 1100
988 1497
991 1058
991 2797
992 1046
994 1800
997 1339
998 1815
999 1360
999 1804
1000 1020
1001 1863
1002 1571
1002 1848
1004 1434
1004 1610
1004 1745
1005 1185
1008 1469
1009 1586
1009 1868
1009 1996
1010 1311
1010 1676
1011 1044
1011 2523
1012 1185
1012 1233
1012 2487
1012 2776
1013 1039
1013 1046
1013 1204
1013 1448
1013 1519
1014 1670
1015 1398
1017 1484
1017 2806
1018 1085
1019 1039
1020 1173
1020 1808
1021 1909
1023 1487
1023 1618
1023 1698
1023 1720
1024 1262
1024 1559
1024 2958
1025 1269
1025 1322
1026 1559
1027 1384
1027 2423
1028 1115
1028 2689
1029 1410
1030 1076
1030 1145
1030 1160
1030 2775
1031 1581
1033 1063
1034 1082
1034 1519
1035 1772
1038 1637
1040 1201
1040 2868
1043 1656
1043 1965
1044 1418
1046 1557
1046 1942
1047 1050
1049 1369
1049 1919
1050 1220
1051 1398
1051 1498
1051 1739
1052 1471
1052 1858
1055 1474
1056 2035
1058 1880
1060 1223
1060 1500
1060 1769
1061 1447
1062 1409
1062 2391
1062 2620
1063 1137
1063 1604
1064 1595
1065 1238
1065 1519
1067 1925
1069 1117
1070 1261
1070 1655
1071 1311
1071 1883
1072 1291
1072 1380
1073 1860
1073 2059
1074 1172
1074 1272
1074 1301
1074 1578
1074 1686
1074 1990
1076 1416
1077 1989
1078 1422
1078 1644
1079 1581
1080 2466
1083 1624
1083 1846
1084 1294
1085 1552
1085 1740
1086 1181
1086 1514
1086 2287
1088 1471
1089 2112
1090 1980
1091 2609
1092 1361
1092 1545
1092 2177
1093 1783
1093 2619
1094 1431
1096 2021
1097 1255
1097 1554
1098 1611
1098 1827
1099 1888
1100 1396
1101 1145
1102 1386
1102 2042
1102 2723
1104 1157
1104 1174
1104 1791
1104 2582
1105 1230
1106 1895
1106 1931
1106 2826
1107 2684
1108 1326
1108 1640
1108 1887
1109 1266
1109 2046
1110 2354
1110 2657
1111 1768
1112 1980
1113 1155
1113 1157
1113 1560
1113 1903
1115 2123
1115 2279
1116 1304
1118 1261
1118 1469
1119 1388
1119 1916
1119 2067
1120 1899
1121 1281
1121 1931
1122 1631
1123 1955
1125 1299
1125 1338
1125 2062
1126 1623
1126 2184
1127 2059
1128 1798
1129 2040
1129 2041
1129 2112
1129 2216
1131 1926
1132 2081
1132 2114
1133 1374
1134 1714
1135 2878
1136 1673
1137 1774
1138 2749
1139 1613
1139 1622
1139 1635
1140 1319
1141 1994
1141 2256
1142 1172
1142 1477
1142 1478
1142 1767
1146 1950
1148 1172
1148 1541
1148 1597
1149 1892
1149 1929
1150 1587
1150 1891
1151 1984
1151 2124
1152 1611
1154 1263
1154 1525
1155 1978
1155 2001
1156 1427
1158 1637
1159 1419
1159 2209
1162 2257
1162 2533
1163 1223
1165 1482
1166 2281
1167 1218
1168 1398
1169 1400
1169 1547
1170 1367
1170 1502
1170 2029
1171 2054
1172 2056
1172 2151
1173 1648
1173 1859
1174 1748
1174 1779
1174 2971
1176 1657
1178 1999
1178 2051
1179 1217
1179 1474
1179 1905
1180 1564
1180 1869
1181 1273
1181 1989
1182 1855
1182 2007
1183 1241
1185 1468
1185 1865
1187 2139
1187 2284
1190 1243
1190 1967
1190 1978
1191 1793
1191 1990
1192 1314
1194 1570
1194 2078
1194 2740
1195 1923
1196 1282
1196 1295
1196 1959
1197 1311
1198 1465
1198 1671
1199 1917
1201 1724
1201 1751
1202 1372
1202 1772
1204 1397
1205 1308
1205 1879
1205 2118
1207 2229
1208 1365
1208 2050
1210 1362
1210 1755
1210 2058
1210 2059
1213 1294
1216 1415
1216 1472
1218 1843
1218 2312
1219 1229
1219 1540
1219 1786
1219 2337
1220 1530
1220 1757
1221 1729
1221 2101
1221 2129
1221 2805
1222 1996
1222 2244
1222 2391
1225 1399
1225 2101
1225 2206
1226 1581
1226 1593
1226 1824
1227 1507
1227 1956
1228 1252
1229 1606
1230 1639
1230 2324
1231 1517
1231 1628
1231 2566
1233 1794
1235 1848
1236 1742
1238 1357
1240 2113
1243 1927
1244 1387
1244 2468
1246 1681
1246 2236
1247 1393
1247 1533
1247 1582
1247 2391
1249 1750
1249 2087
1249 2189
1250 1751
1251 1651
1251 1677
1251 1753
1251 1989
1251 2124
1252 1302
1252 1447
1253 2093
1254 1416
1254 2090
1256 1949
1257 1330
1257 1658
1257 2021
1258 1388
1258 1985
1258 2479
1259 2576
1260 1944
1261 1712
1262 1563
1264 1548
1264 1714
1264 1841
1265 1558
1265 1583
1265 2321
1266 2391
1267 1394
1268 1374
1268 1846
1270 2070
1270 2461
1272 1564
1272 1765
1273 2060
1275 2311
1276 1373
1276 2330
1277 1571
1277 1720
1277 1930
1278 1670
1278 2314
1280 1697
1280 2028
1281 1829
1282 1948
1282 2326
1284 2015
1286 2169
1288 1876
1289 1961
1291 1622
1292 1574
1294 2030
1294 2221
1295 1726
1295 1922
1295 2168
1295 2445
1296 2072
1301 1744
1302 1562
1302 1581
1303 1353
1303 1873
1303 1935
1303 2584
1304 1355
1304 1389
1306 1901
1306 2158
1306 2390
1307 2255
1308 2257
1309 1688
1309 1925
1310 1322
1310 2042
1310 2856
1311 1579
1311 2601
1312 2369
1314 2485
1315 1751
1318 2391
1319 1710
1321 1554
1321 2460
1322 1384
1324 1631
1325 2381
1325 2619
1326 2023
1329 1414
1329 1573
1329 1809
1332 1894
1333 2387
1335 1616
1335 1785
1335 2644
1336 1440
1339 1370
1339 2037
1340 1360
1340 2472
1341 1537
1343 1350
1343 2194
1346 1813
1347 1608
1347 2084
1348 1933
1348 2589
1349 1657
1349 1963
1349 2765
1350 1389
1350 1706
1352 2262
1354 2386
1355 1752
1356 1423
1356 1452
1358 1545
1358 1617
1358 2045
1359 1632
1359 2125
1360 2061
1360 2167
1361 2092
1361 2177
1363 1994
1363 2181
1365 1582
1365 1777
1366 1496
1366 1992
1367 2368
1367 2408
1368 1685
1369 2425
1370 1396
1370 2587
1372 1698
1374 2309
1375 1404
1375 2129
1376 1873
1379 1453
1382 1723
1382 2170
1383 2405
1384 1749
1385 1501
1385 2217
1386 1569
1386 2937
1388 1808
1390 1550
1391 2093
1392 1714
1392 1732
1392 2117
1394 1962
1394 2107
1395 1566
1395 2710
1398 1506
1399 1651
1401 2762
1402 1423
1402 2108
1403 2292
1404 1527
1404 2022
1404 2052
1405 1781
1405 2584
1407 2595
1407 2822
1408 1889
1408 1913
1408 1922
1409 1945
1409 2420
1412 2128
1413 2752
1414 1428
1414 2578
1415 1974
1415 2580
1416 1890
1418 2084
1418 2700
1419 1682
1419 1722
1419 1750
1419 1942
1419 2352
1421 1555
1421 2118
1424 1491
1424 1508
1427 1501
1427 1636
1427 1990
1427 2962
1428 1745
1428 2600
1430 1872
1430 2416
1430 2812
1431 1780
1431 2107
1432 1954
1432 2130
1433 2207
1435 2274
1440 1708
1443 1526
1443 1639
1445 1750
1445 2389
1446 1778
1447 2329
1448 1494
1448 1764
1448 2792
1449 1671
1449 2271
1449 2348
1450 1658
1453 1478
1453 1712
1453 1966
1456 2175
1457 2250
1457 2689
1458 1963
1458 1997
1459 2038
1460 1863
1460 1917
1461 1873
1461 2000
1461 2429
1462 1651
1462 2408
1463 2231
1464 1844
1465 2258
1465 2406
1466 1744
1467 2674
1468 1578
1468 2445
1469 2109
1469 2824
1470 1900
1470 2100
1470 2925
1471 2595
1472 1831
1472 2142
1472 2175
1472 2322
1473 1491
1473 2657
1475 2277
1475 2553
1475 2942
1476 2236
1477 2410
1480 1514
1482 1617
1482 1884
1484 1495
1484 1573
1484 2050
1484 2927
1485 2012
1485 2883
1487 1765
1487 2219
1487 2407
1488 2245
1490 1586
1490 2898
1491 1918
1491 2040
1493 1564
1493 1615
1493 2148
1493 2619
1494 2257
1496 2369
1497 1547
1497 1627
1498 1841
1498 2472
1500 1922
1500 2146
1501 1789
1502 2160
1502 2626
1503 1702
1503 1986
1503 2135
1503 2464
1503 2942
1504 1726
1504 2188
1505 1819
1505 2284
1506 1532
1506 2120
1507 1523
1507 1699
1507 1896
1507 1930
1507 2483
1508 1745
1509 2881
1510 1980
1513 1609
1513 1988
1513 2551
1515 2574
1518 2424
1518 2808
1519 2102
1520 2430
1522 1648
1522 2230
1522 2268
1522 2995
1524 1621
1524 1868
1524 2199
1525 1569
1526 1528
1527 1552
1527 2185
1529 1754
1529 1987
1529 2923
1532 1797
1533 1810
1533 2455
1535 2899
1536 2829
1537 1716
1538 2987
1540 1752
1540 2033
1541 2110
1541 2121
1542 2183
1542 2187
1543 2637
1545 2490
1545 2594
1545 2856
1546 2431
1547 1705
1547 1742
1547 1967
1547 2383
1548 2886
1549 2168
1550 2143
1550 2872
1551 1791
1551 2210
1553 2107
1554 1602
1554 2235
1555 2151
1557 1778
1557 1794
1557 2388
1559 1609
1559 2394
1559 2419
1560 2189
1561 1795
1561 1847
1561 2374
1562 1942
1564 2035
1564 2691
1566 1955
1567 1997
1568 1661
1568 2929
1569 1816
1569 2084
1569 2393
1570 1910
1571 1573
1571 1791
1572 2249
1574 1586
1574 2079
1576 2343
1578 1780
1578 1976
1578 2172
1580 2096
1581 1760
1582 1841
1583 2047
1585 1926
1585 1948
1585 2684
1586 1776
1586 2206
1588 2394
1589 2261
1589 2510
1589 2761
1590 1955
1590 1960
1590 2172
1591 2003
1593 1609
1594 1622
1594 2295
1594 2559
1595 1892
1595 2077
1596 2413
1597 2539
1599 1693
1599 1935
1599 2122
1601 2555
1602 2507
1602 2808
1604 2619
1606 1771
1606 1958
1607 1702
1607 2811
1608 1728
1609 1888
1609 1992
1610 1780
1611 1672
1613 2288
1613 2804
1614 2135
1615 2082
1616 1836
1617 1635
1619 1791
1619 2050
1621 2985
1622 2134
1622 2176
1622 2215
1622 2748
1622 2836
1623 2303
1627 2747
1629 2897
1630 1801
1630 2657
1630 2808
1631 2026
1632 1930
1632 2995
1633 2133
1635 1963
1635 2101
1635 2301
1636 2570
1636 2597
1637 2142
1638 2114
1639 2292
1640 2610
1647 1833
1648 2561
1651 1657
1651 2203
1651 2224
1652 1891
1654 1751
1656 1700
1656 1906
1657 2001
1658 1666
1658 1827
1658 1896
1659 1691
1660 1674
1660 2100
1661 2732
1664 2267
1665 1859
1665 2050
1665 2585
1666 1903
1666 1937
1667 1987
1668 2938
1670 2696
1670 2698
1671 1723
1673 1706
1673 2146
1675 1709
1676 2170
1679 1710
1679 1787
1679 2697
1680 2008
1680 2284
1681 1966
1681 2055
1681 2322
1682 1914
1683 1739
1683 2116
1684 1982
1684 2272
1685 1722
1686 2318
1686 2377
1688 2650
1690 2005
1691 1865
1691 2246
1692 1743
1692 2801
1693 2227
1693 2926
1694 2800
1694 2958
1696 2346
1697 1834
1698 1884
1698 2008
1699 1897
1699 2326
1700 1724
1700 2054
1700 2429
1700 2526
1700 2920
1701 2183
1702 1913
1702 2145
1702 2269
1703 1972
1704 1926
1704 2397
1706 2443
1707 2826
1708 1965
1709 2746
1711 2934
1712 1819
1712 2340
1713 2773
1714 2241
1714 2950
1715 1999
1715 2245
1715 2999
1716 1726
1716 2077
1716 2267
1716 2712
1717 2282
1717 2570
1718 2175
1719 2679
1723 1936
1723 2703
1724 2097
1724 2658
1724 2951
1725 2399
1725 2427
1726 2376
1727 1934
1727 2489
1728 2063
1728 2281
1729 1813
1729 1964
1731 1768
1731 2134
1732 2160
1732 2338
1732 2903
1733 1930
1735 1736
1737 2315
1738 1967
1739 2874
1741 2031
1741 2991
1742 1773
1742 2314
1742 2992
1743 2122
1744 1769
1745 1770
1745 1874
1745 2124
1745 2263
1746 1786
1749 1814
1752 2321
1753 2597
1755 2279
1755 2486
1755 2708
1755 2923
1755 2945
1756 2358
1757 2892
1758 2587
1758 2836
1759 1920
1759 2428
1760 2004
1761 2602
1762 2301
1762 2848
1763 2437
1763 2564
1765 2493
1768 2262
1768 2275
1769 2579
1769 2874
1770 2078
1770 2314
1771 1876
1773 2368
1774 1984
1776 2011
1777 2687
1777 2977
1779 1943
1779 2632
1780 1972
1780 2265
1781 2213
1782 2133
1784 2156
1784 2980
1785 2057
1785 2515
1786 1822
1786 2227
1787 2347
1788 2463
1788 2586
1789 2531
1791 2374
1791 2653
1792 2270
1792 2422
1794 2409
1794 2600
1795 2282
1795 2646
1795 2919
1796 2112
1796 2554
1798 2320
1800 2053
1800 2872
1801 2181
1801 2542
1801 2826
1802 1854
1802 2309
1803 2424
1803 2888
1804 2301
1805 2988
1806 2269
1807 1929
1807 2315
1810 1990
1811 1930
1813 1872
1816 2478
1818 2263
1818 2344
1819 2181
1819 2552
1820 2558
1823 1825
1823 2114
1824 2174
1824 2835
1825 2065
1826 2175
1827 1946
1829 2413
1829 2616
1834 1862
1834 2395
1834 2660
1836 2703
1838 1943
1840 2352
1840 2587
1841 2099
1843 2924
1844 1876
1844 1901
1844 2237
1847 2066
1848 2169
1849 2715
1849 2904
1850 2766
1851 2681
1852 1869
1852 2278
1852 2493
1853 1928
1853 2773
1855 2450
1855 2924
1856 2060
1856 2355
1858 1959
1858 2566
1858 2764
1860 2243
1861 1873
1861 1888
1861 2308
1863 2122
1864 1889
1865 2014
1865 2537
1866 2469
1866 2507
1868 2518
1868 2979
1870 2307
1870 2699
1870 2988
1871 2961
1874 2294
1875 2145
1875 2280
1876 2172
1879 2014
1879 2384
1879 2831
1880 2150
1880 2972
1883 2411
1885 2427
1886 1982
1886 2735
1887 2380
1887 2392
1889 2291
1889 2832
1890 2564
1891 2928
1892 2300
1893 2110
1893 2876
1894 2995
1895 2408
1896 2217
1896 2693
1897 2896
1898 2313
1898 2734
1900 2304
1900 2616
1900 2812
1900 2937
1901 2795
1901 2851
1902 2280
1905 2276
1907 2970
1908 2103
1908 2335
1910 1961
1910 2934
1912 1955
1912 2023
1914 2134
1915 2485
1915 2948
1916 2422
1920 2190
1920 2704
1921 2076
1922 2281
1922 2991
1923 2133
1925 2413
1926 2253
1927 1948
1927 2495
1928 2568
1929 2007
1930 2160
1931 2412
1932 2731
1935 2210
1935 2590
1936 2354
1936 2953
1938 2788
1940 2047
1941 2363
1942 2549
1943 2084
1943 2130
1943 2762
1944 2699
1947 2101
1948 2019
1952 2939
1953 2281
1953 2339
1953 2370
1953 2877
1954 2398
1954 2800
1955 2071
1959 2244
1960 2246
1962 2037
1962 2048
1962 2148
1963 1981
1963 2034
1963 2091
1964 1976
1965 2235
1966 2036
1966 2471
1967 2470
1969 2997
1970 2729
1971 2283
1972 2064
1972 2416
1972 2954
1973 2083
1973 2348
1974 2161
1975 2148
1975 2354
1977 2154
1977 2486
1978 2171
1979 2088
1979 2146
1980 2625
1982 2630
1983 2811
1987 2151
1987 2460
1993 2361
1995 2014
1995 2940
1996 2406
1996 2831
1997 2110
1998 2956
1999 2553
1999 2816
1999 2926
2000 2505
2000 2703
2000 2733
2003 2014
2003 2135
2003 2998
2004 2013
2005 2633
2006 2176
2006 2648
2007 2292
2008 2117
2011 2042
2011 2061
2011 2273
2012 2348
2013 2583
2015 2391
2016 2175
2017 2048
2017 2992
2018 2647
2019 2155
2020 2022
2024 2116
2024 2283
2026 2921
2028 2768
2029 2968
2031 2797
2032 2265
2033 2075
2034 2101
2034 2751
2037 2162
2038 2412
2038 2466
2039 2369
2040 2737
2041 2331
2043 2672
2043 2898
2045 2209
2045 2852
2047 2049
2047 2099
2047 2414
2048 2117
2048 2300
2048 2804
2049 2836
2050 2387
2051 2123
2051 2153
2052 2284
2052 2854
2054 2840
2056 2166
2056 2625
2057 2972
2058 2285
2058 2586
2062 2448
2062 2952
2067 2138
2067 2306
2067 2435
2068 2942
2070 2466
2070 2725
2070 2767
2071 2109
2071 2268
2072 2157
2073 2504
2074 2237
2076 2407
2077 2391
2077 2584
2081 2140
2081 2254
2081 2324
2081 2775
2083 2356
2083 2464
2084 2134
2086 2525
2089 2889
2090 2948
2091 2501
2092 2096
2093 2254
2095 2669
2096 2467
2098 2781
2099 2860
2100 2231
2102 2130
2102 2600
2103 2377
2103 2796
2104 2168
2104 2331
2104 2357
2106 2253
2107 2126
2107 2259
2107 2466
2109 2480
2110 2430
2111 2633
2112 2681
2113 2638
2114 2345
2119 2206
2120 2183
2122 2485
2122 2616
2122 2781
2123 2404
2125 2163
2125 2221
2125 2845
2126 2955
2127 2996
2130 2471
2132 2473
2133 2904
2134 2384
2136 2248
2136 2905
2137 2286
2139 2727
2140 2802
2140 2807
2140 2986
2141 2220
2147 2514
2149 2181
2150 2535
2152 2164
2152 2612
2152 2851
2153 2994
2154 2787
2154 2986
2155 2562
2158 2200
2158 2571
2158 2799
2162 2523
2163 2560
2164 2311
2165 2395
2165 2543
2166 2170
2168 2169
2170 2272
2171 2288
2172 2922
2174 2567
2175 2245
2177 2179
2177 2183
2177 2314
2181 2680
2182 2192
2183 2281
2184 2426
2184 2553
2185 2191
2185 2260
2186 2829
2187 2536
2189 2302
2189 2569
2190 2239
2190 2406
2196 2351
2196 2838
2200 2535
2203 2412
2204 2352
2204 2416
2208 2837
2209 2282
2210 2421
2212 2798
2213 2829
2215 2422
2217 2251
2217 2712
2219 2302
2221 2281
2226 2414
2226 2428
2228 2628
2228 2982
2232 2292
2232 2340
2232 2528
2232 2684
2235 2932
2237 2240
2237 2406
2239 2882
2240 2603
2241 2423
2241 2501
2241 2602
2241 2914
2245 2576
2248 2864
2249 2261
2250 2316
2255 2475
2257 2430
2257 2446
2257 2497
2259 2430
2260 2715
2261 2458
2262 2491
2266 2572
2267 2532
2268 2648
2269 2282
2269 2362
2270 2359
2271 2339
2272 2652
2272 2745
2273 2629
2275 2308
2275 2379
2279 2592
2281 2801
2282 2535
2284 2528
2285 2756
2286 2414
2287 2593
2287 2773
2288 2471
2291 2453
2294 2486
2294 2553
2296 2380
2299 2527
2300 2593
2300 2895
2301 2304
2306 2479
2306 2519
2308 2403
2308 2678
2313 2862
2314 2343
2315 2570
2316 2583
2316 2613
2316 2630
2317 2515
2321 2379
2323 2971
2324 2419
2324 2974
2325 2490
2325 2511
2325 2869
2326 2632
2327 2911
2328 2663
2333 2761
2337 2821
2338 2509
2340 2494
2341 2447
2341 2896
2344 2986
2346 2596
2346 2634
2348 2730
2350 2458
2354 2579
2355 2545
2356 2949
2357 2420
2357 2784
2359 2629
2359 2683
2359 2783
2362 2494
2367 2418
2367 2454
2369 2804
2370 2678
2370 2766
2370 2770
2371 2884
2373 2473
2373 2581
2374 2482
2379 2541
2379 2662
2379 2666
2380 2470
2381 2544
2382 2422
2382 2961
2383 2771
2388 2469
2388 2481
2392 2694
2393 2649
2397 2487
2398 2706
2399 2543
2405 2834
2405 2894
2407 2509
2407 2774
2408 2835
2416 2545
2417 2563
2419 2469
2420 2659
2420 2737
2421 2716
2421 2829
2422 2615
2422 2805
2424 2793
2425 2427
2427 2577
2428 2491
2428 2617
2430 2436
2430 2477
2432 2487
2433 2944
2434 2679
2437 2603
2439 2482
2439 2663
2442 2703
2448 2974
2449 2545
2449 2682
2454 2854
2458 2493
2460 2870
2465 2705
2468 2508
2468 2804
2469 2728
2469 2834
2471 2695
2478 2548
2479 2900
2488 2616
2494 2795
2496 2525
2497 2556
2502 2750
2502 2849
2503 2611
2505 2819
2512 2579
2513 2846
2514 2659
2519 2801
2520 2625
2524 2964
2525 2768
2525 2885
2526 2600
2527 2688
2531 2610
2531 2667
2532 2958
2535 2976
2536 2598
2539 2543
2539 2663
2541 2911
2543 2595
2544 2752
2544 2769
2547 2754
2547 2873
2556 2714
2565 2824
2568 2569
2569 2640
2571 2955
2572 2796
2574 2603
2575 2973
2577 2723
2577 2929
2577 2941
2579 2761
2581 2717
2585 2586
2587 2760
2588 2743
2588 2755
2589 2621
2589 2678
2590 2730
2591 2777
2592 2602
2593 2658
2595 2849
2597 2863
2598 2734
2598 2794
2602 2884
2602 2909
2604 2768
2605 2850
2606 2714
2609 2954
2612 2782
2616 2720
2617 2757
2623 2826
2626 2718
2628 2661
2629 2723
2630 2762
2630 2868
2641 2675
2641 2786
2643 2834
2665 2689
2665 2972
2670 2687
2671 2677
2686 2702
2688 2713
2696 2718
2697 2749
2701 2757
2701 2806
2702 2939
2703 2761
2708 2960
2709 2927
2711 2799
2717 2942
2718 2734
2724 2735
2729 2911
2730 2983
2731 2807
2732 2768
2733 2734
2745 2992
2752 2873
2752 2946
2766 2819
2771 2908
2772 2932
2775 2848
2777 2825
2780 2884
2780 2898
2780 2961
2781 2937
2783 2788
2787 2934
2811 2818
2812 2852
2823 2905
2824 2869
2825 2873
2833 2847
2850 2949
2851 2901
2851 2989
2855 2899
2855 2939
2856 2889
2858 2946
2858 2990
2878 2903
2884 2889
2889 2993
2894 2927
2895 2914
2901 2938
2905 2916
2905 2985
2914 2928
2925 2949
2927 2984
2938 2940
2960 2970

This code has right logic. however it times out on acceptance timing. Did I just miss some basic thing in question ? or how can I further optimize this code ?

I can understand power of parallelStream comes from underlying hardware and number of cores in CPU. This doesn't perform too bad on my system.

cpu profiling shows most of the time spent in equals() (the custom one) method

\$\endgroup\$
  • 2
    \$\begingroup\$ Please include the problem statement in the post itself, or otherwise describe what the code is doing. \$\endgroup\$ – Mathieu Guindon May 28 '17 at 14:52
  • \$\begingroup\$ @Mat'sMug I have added problem statement into the question. It is readable. Due to images inserted in question I am not able to copy and paste text version. \$\endgroup\$ – user3833308 May 28 '17 at 18:40
  • \$\begingroup\$ I suspect it's more because of the huge dataset, your post must near the 65K character limit - you could put up the problem statement and then present your solution, and link to a github repository that includes the full dataset, for those who want/need additional context; the dataset isn't really up for review anyway ;-) \$\endgroup\$ – Mathieu Guindon May 28 '17 at 18:51
  • \$\begingroup\$ you can't really answer these questions without an objective of what you are trying to solve. do you want to make your code super fast / efficient, or do you want to make it easy to maintain? What are the consequences of mistakes? Those decisions alone will change the code you write. \$\endgroup\$ – BKSpurgeon May 29 '17 at 9:16
  • \$\begingroup\$ super fast. <!---> \$\endgroup\$ – user3833308 May 29 '17 at 21:02
4
\$\begingroup\$

General tips:

  1. You have the data set apparently, profile and see where the time is spent.
  2. Determine the time complexity of your algorithm.
  3. These types of problems almost never require you to "optimize" your code to make it faster, they need you to nail the correct algorithm. Let me rephrase that, even a shitty, most sub-optimal implementation of the correct algorithm with the right time complexity will likely pass the time requirement (in fact this is typically one of the design goals when making the data sets: A poor implementation of the right algorithm must pass while a super optimized version of the wrong algorithm must fail).
  4. If you're getting time limit exceeded, you most likely have the wrong algorithm and time complexity or you have a bug (infinite loop or w/e).

With that in mind, I didn't read your code too carefully but just looked for the obvious problem sites. For example I see this bit of code:

    for (int i = 0; i < string1.length(); i++) {
        for (int j = i + 1; j < string1.length(); j++) {
            if (arr1[i] == arr1[j]) {
                if (arr2[i] != arr2[j]) {
                    return false;
                }
            } else if (arr2[i] == arr2[j]) {
                return false;
            }
        }
    }

You can be certain that they have constructed a test case which never terminates early from the returns and you must infact run all the \$O(n^2)\$ iterations. So without reading the problem description, nor the rest of the code. I'm going to guess that there's your problem and they expect you to do better than \$O(n^2)\$.

\$\endgroup\$
  • \$\begingroup\$ I am aware of all general advices. and I do believe your point 3. is where I am incorrect. I have added problem statement in the question. if you could help me point out code optimization. \$\endgroup\$ – user3833308 May 28 '17 at 18:39
  • \$\begingroup\$ @user3833308 I did point out where you should optimize and your profile data agrees. As the question is a programming challenge question I cannot give you the right algorithm as that would defeat the challenge part. However I can give you a hint, try to think about the similarity of the strings, what does it mean? Can you determine it without checking all the pairs? \$\endgroup\$ – Emily L. May 28 '17 at 22:45
  • \$\begingroup\$ I already know that part. Thanks. can you help little more with hint ? \$\endgroup\$ – user3833308 May 29 '17 at 23:10
  • \$\begingroup\$ Other solution I have is to manage character -> indices map. and then compare values of that map iterating over key set in sequential order. which is slower than current solution \$\endgroup\$ – user3833308 May 29 '17 at 23:25
  • \$\begingroup\$ @user3833308 If you have string a = "axaxxa" and string b="1y2yy3". Then for the strings to be similar, 1, 2 and 3 in string b must be the same character, and that character must not occur anywhere else in b. Otherwise a[i]==a[j] -> b[i] ==b[j] doesn't hold... Can you find any other such relations or rules that can help you? \$\endgroup\$ – Emily L. May 30 '17 at 12:44
1
\$\begingroup\$
    private static boolean equals(String string1, String string2) {
        char[] arr1 = string1.toCharArray();
        char[] arr2 = string2.toCharArray();

        for (int i = 0; i < string1.length(); i++) {
            for (int j = i + 1; j < string1.length(); j++) {
                if (arr1[i] == arr1[j]) {
                    if (arr2[i] != arr2[j]) {
                        return false;
                    }
                } else if (arr2[i] == arr2[j]) {
                    return false;
                }
            }
        }
        return true;
    }

As already observed, this is terribly inefficient. The following optimisations occur to me:

Sticking with quadratic time

  • If you have a string of the form AABCA you don't need to do three comparisons to check that the three As are equal: two suffice because equality is transitive. This translates into a continue statement or two in the inner loop.

Reducing to linear time

  • Use a map from character to first index, reduce each string to a list of indices, and compare lists of indices. You say that this is slower, but I don't think you've posted that code so I can't review it.
  • Convert the reference string into a list of indices; e.g. AABCA becomes [0, 0, 2, 3, 0]. Then for each candidate match generate a string according to that list of indices; e.g. ABCDE becomes AACDA; test equality between the expected and candidate strings, and if they're equal test that you have sufficient distinct characters (probably using a HashSet<Character>).

Stepping up a level

  • Rather than trying to match each substring of the correct length, read up on fast string matching (e.g. Knuth-Morris-Pratt) and apply the same principles of discarding multiple positions at a time.
  • You're using a language with a powerful standard library. Rather than manually implementing algorithms like KMP you can exploit the powerful matching tool which is regex.
\$\endgroup\$
  • \$\begingroup\$ added code in question about the alternate solution \$\endgroup\$ – user3833308 May 31 '17 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.